Alejandro Loboguerrero

Patrick Bas
email: patrick.bas@lis.inpg.fr

Joël Liénard
email: joel.lienard@lis.inpg.fr

Iterative Informed Audio Data Hiding Scheme Using Optimal Filter

Keywords: watermarking (audio), spread spectrum, datahiding (audio.) I

Audio watermarking is a method that allows the insertion of an imperceptible mark on an audio data set. Although the watermarking is often used to guarantee copyrights, it can also be used to increase the information transmitted in a communication context. In typical watermarking applications, the audio data set represents the host that supports the embedded information and it is considered as "noise". However, we can use the fact that this signal is not random but completely known at the transmitter to reduce imperceptibility and improve robustness. Based on this idea, we derive a model from a classical data transmission technique and we take advantage of the knowledge of the host information to design an informed embedding scheme. This model has been then improved using an iterative controlling of the transmitted power and optimal filter. This informed embedding scheme allows us to provide a robust data-hiding system for several treatments, and it's compared to non informed and matched filter embedding schemes.

INTRODUCTION

Watermarking is usually presented as a copyright protection technique. The basic idea consists on adding a mark (also called a signature) into the data to be protected [START_REF] Basia | Robust Watermarking in time domain[END_REF]. This mark must be unoticiable: it's not allowed to include any audible distortion while treating audio signals. Audio watermarking must also be robust to usual signal processing as well as to the malevolent attacks. However, this mark must be detectable by the authorized people.

In addition to its use for copyrights protection, the watermarking techniques can be employed in data transmission technologies for audio data hiding purposes [START_REF] Loboguerrero | Implémentation d'un système de tatouage pour la transmission de données[END_REF][START_REF] Boney | Digital Watermarks for Audio[END_REF]. Several applications are possible in this context. For example, if the priority information to be transmitted is the speech voice, then it may be useful to transmit video analysis information such as the lips motion parameters, the speaker's face or any other information identifying the speaking face. Such an application is addressed in the project ARTUS 1 which aims to embed animation parameters into audio and video contents.

II.

A.

1)

1 This project was funded by national RNRT Artus Project In this paper, we want to present an enhanced audio watermarking scheme that is applied to digital communications .

Well defined constraints are required in this framework:

• The transmission rate of the inserted message must be as high as possible. • The inserted message must be imperceptible to the listeners (No audible distortion is permitted). • In addition to channel's noise, detection is perturbed by the audio signal used as support of the information. • The embedded information must be preserved after audio compression. MPEG layer 3 (MP3) will be often used [4].

Contrary to copyright protection based watermarking techniques, the mark embedded message does not represent significant data and consequently is not subject to intentional attacks.

IMPLEMENTATION

General Scheme

The proposed watermarking method relies on a CDMA-like watermarking scheme [START_REF] Proakis | Digital Communications[END_REF]. This technique allows simultaneous multi-user communications and can be also used for low SNR (Signal to noise ratio) monousers applications. It's based on the Spread Spectrum modulation technique that allows a homogeneous power distribution in all available bandwidth.

Embedding

The modulation processes uses just one single code to carry a binary message in this implementation. The values +1 and -1 represent this binary message. Positive version of the code corresponds to bit 1 and, negative version will be used to carry bit 0. (Fig. 1).

Figure. 1 Single Code Modulation

The meaning of this product can be expressed as the calculation of

W(t) = MSG(t) × C(t) (1)
In this equation MSG(t) represents the message that will be sent, C(t) the single code and W(t) the signal obtained from modulation process. This signal W(t) is then added to the speech signal to provide S w (t).

S w (t) = S(t) + W(t)

(2)

In order to diminish the audibility of the message, the inserted codes have to fulfill several power and spectral distribution requirements. These conditions will be studied further in this paper.

2) Optimal Detection

At the reception stage, the SNR has been maximized. This is done in complement of the classical spread spectrum data hiding scheme in which the noise is considered to be white and gaussian. In data hiding applications, the audio signal plays the role of a noise. In fact, this "noise" (music, speech) has a very dynamical frequency behavior and it can be treated in an optimized way by the use of the Optimal Filter [START_REF] Max | Methodes et Techniques de Traitement du Signal et Applications aux Measures Physiques[END_REF].

This kind of filtering maximizes the SNR for signals immerged in a non-white noise. The equation characterizing this filter is:

( ) ( ) ( ) f S f C f Fop s fT e π 2 * = (3)
This filter can be described in two parts. The first one has been noted as C*(f)e 2πfT and it is the matched filter to the sent signal C(t). The argument of the exponential represents a temporal delay and T is the signal duration. The second one, noted as S s (f) refers to a whitening process of the audio signal. In fact, it denotes the Spectral Power Density SPD of the signal to be whitened.

The detection is then computed by convolution of the received signal (sent signal + channel noise) with the Optimal Filter. This convolution is then sampled every T seconds in a synchronized way. The decision will be taken by comparing its value with a threshold fixed beforehand. The result of this operation will be called Y(t).

In this system the value of the threshold is zero (binary message). The decision law is described by the two classical following equations:

0 ) ( ) ( > ⊗ =T t w f S f Fop If ⇒ Detected Bit = 1 (4) 0 ) ( ) ( < ⊗ = T t w f S f Fop If ⇒ Detected Bit = 0 B. 1)
Additional Improvements Once the watermarking method has been defined, several modifications have been implemented in order to enhance the system behavior. The main idea of this implementation lies on the use of the value of each sound realization to attain the desired conditions. The resulting scheme is refered as informed embedding scheme [START_REF] Miller | Informed Embedding: Exploiting Image and Detector Information During Watermark Insertion[END_REF] because the host signal is used to construct the emedded mark. This scheme has been improved take into account the modifications included by this implementation (informed embedding). This amelioration has been donde in a iterative way yielding to an the iterative informed data hiding scheme. This process can be decomposed in four stages:

1. Controlling the Codes Power.

2. Iterative Adjusting of the Power Control.

3. Spectral weighting of the code by the use of a human like psychoacoustics model.

A synchronization stage will be also presented

Informed Embedding by Codes Power Control

The proposed strategy allows us to minimize the perception of the added message. This is done by finding the minimal necessary power to obtain free error detection accordingly with the equations presented in (4). This control power is possible because of the knowledge of the audio signal in the transmission stage. This knowledge allows us to do a deterministic approach to the support signal and calculate the desired values. The use of this amount of power combined with the utilization of a psychoacoustics model guarantees not only free error detection but also a minimal audible distortion. To find this quantity of power, it is necessary to determinate the minimal coefficient value for which each code must be multiplied. Based on the equations (4) (Detection System) the Calculation yields the following result:

( ) ( ) ( ) ( ) T t m t Fop W t Fop S K = ∫ ∫ ∂ - ∂ - - ≥ τ τ τ τ τ τ τ τ (5)
In this equation C m denote the code weighted by the human psychoacoustics model, F op is the same as in (3).

In the Fig. 2, the region labeled "informed embedding" represents the calculation of K is done from a local replica of the detection system.

The modifications yield by this implementation affect the final design of the scheme, particularly the message detection step and the implementation of the psychoacoustics model. Before explaining those points, it is important to clarify the generated modifications.

• Modification of S s (t). In the equation (4) the Spectral Power Density of S(t) and is substitued by S w (t)+N(t). Although there is a little difference between them, it can generate a high number of errors. The calculation of the coefficient K (5) was thus modified in order to decrease the effect produced by this approximation. This is explained in the paragraph 2). • Modification of W m (t). In reception, It is necessary to determine the appearance of the transmitted code. This code has been spectralweighted by the psychoacoustics model (stage 3)). To that end, we have assumed that the difference obtained while computing the psycoacoustics model from S(t) and that one computed from S w (t) is negligible. This assumption has been corroborated by the final tests.

2) Power Control by Iterative System

We have modified the calculation of K regarding the difference between the desired and available Spectral Power Density. The idea is to recalculate the necessary power from the modified Spectral Power Density called S s+w obtained from S s +W(f). This development takes us to the implementation of the iterative system represented in the Fig. 2 by the region labeled "Informed Iterative Embedding". The block "computation of K" shown in this figure is the same as that one described in [START_REF] Miller | Informed Embedding: Exploiting Image and Detector Information During Watermark Insertion[END_REF]. While calculating every single iteration, the system affects the computation until free error detection has been attained.

The resulting equations are:

T t i i i i t Fop W K t Fop S K = + ∫ ∫ ∂ - ∂ - - ≥ τ τ τ τ τ τ τ τ ) ( ) ( ) ( ) ( 1 (6) ( )         = + - ) ( ) ( * 2 1 f f C t Fop S e TF KiW s fT i π (7) With K 0 =1. 3) 4) C.

Psychoacoustics Model

The psychoacoustics stage allocates the spectral representation of the code in the frequencies where the human audio system is less sensitive. This is done by a frequency modulation of the code using a model derived from the compression standard MPEG-1 [START_REF] Painter | A Review of Algorithms for Perceptual Coding of Digital Audio Signals[END_REF]

Synchronization

The synchronization stage is guaranteed by the addition of a synchronization code that is detected using classical sliding correlation techniques.

Definitive Implementation

Once we have totally developed each one of the stages involved in this development we can do a presentation of the final scheme (Fig. 3). In the second test, the matched filter has replaced the optimal filter. The obtained power ratio compared to the result obtained in the first test allows us to compare the performances between the optimal and matched filter.

The third test is done to compare the behavior of our informed power control system vs. a classic implementation (open loop with constant power). In order to achieve this, we have used the constant power that is necessary to obtain the same number of errors and we have measured the Signal to Message Ratio. The comparison between the obtained power ratio and the first test shows the desired result.

Ten signals have been processed and the obtained results have been evaluated for a bit rate of 86 bit/s. The used sounds have been sampled to 44.1 kHz for 16 bitsbytes and resultant files have 116 seconds duration every one. This corresponds to a 10.000 information bits sent.

The Chart No. 1 synthesizes these results in dB's.

Although this implementation guarantees free error detection in the case of an ideal channel without additive noise, an Additive Gaussian Noise Channel (AGNC) with a SNR of 40 dB's has been simulated. In order to consider this eventual presence of noise, the computation of K has been adjusted. The BER obtained is 0.082. In these conditions the added message stays inaudible. V.

CONCLUSIONS AND PERSPECTIVES

The data-hiding scheme based on the deterministic knowledge has been presented. The fact that the optimal filtering detection is more performant that than the classical correlation detector has been corroborated by measuring the necessary power for free error detection. By the other hand, this approach outlines the fact that the audio host can be treated in a different way from a noise. An iterative data hiding system has been developed based on this idea and it has been shown that acceptable bit rates can be reached without perceptible audio distortion using this technique. This is idea can be used to improve the performances of the system synchronisation.

Figure 2 .

 2 Figure 2. Informed Embedding and Iterative Embedding

Figure 3 .

 3 Figure 3. Definitive Implementation

Chart No. 1

 1 Obtained Signal to Message Ratios (dB's)IV.


Appasamy Murugaiyan
email: a.murugaiyan@wanadoo.fr

Object of donation in Tamil epigraphic texts (10th -11th centuries): Exploring the interaction between syntax and information structure 1

Keywords: accusative, marked object, focussed object, relativization, information structure I

Object of donation in Tamil epigraphic texts (10th -11th centuries): Exploring the interaction between syntax and information structure

Appasamy Murugaiyan

In our analysis of early Tamil epigraphic texts, we have come across two distinct structures concerning the object of a verb: (1) The regular pattern, where the direct object, whether accusative marked or not, is placed to the left of the verbal predicate, thus corresponding to the presumed canonical SOV constituent order in Dravidian and (2) The focussing pattern where the object, unmarked for accusative, is placed on the right of the predicate. The object of donation is typically encoded in this dislocated noun phrase, extracted from its basic OV position through a relativization process. This right detachment triggers also the phenomenon of quantifier floating, where the quantifier is placed on the right side of the noun head. These changes bring structural symmetries which are used by the information structure to enhance the reading of the inscriptions. The dislocation of 'object of donation' is clearly the result of a discourse strategy. The variation in the order of constituent could be better explained in correlation with factors like historical changes or as a combination of syntactic, semantic and pragmatic (discourse) factors.

In this paper we attempt to explain that the placement of different elements is controlled by the information structure (IS). Information structure concerns the way the information is packaged in discourse depending on the context of communication. The present study is based on data taken from South Indian Inscriptions -Vols. 1, 2 and 13.

In order to make the following discussion clear, we will start by laying out some basic assumptions. In Dravidian, the generally accepted word order -both diachronic and synchronic-is SOV. 3 A commonly made cross-linguistic generalization is that languages with extensive case-marking and rich verbal morphology tend to have greater freedom of word order4 in comparison with languages with `fixed´ word order, like English, which encode grammatical relations directly. In the language of Tamil epigraphic texts, the grammatical form of sentences is motivated by the requirements of information structure which is an essential factor in the identification of donated objects.

II.1. Information structure and Epigraphic texts

Reading and understanding epigraphic texts is based on "PRESUPPOSITIONS and ASSERTIONS" (i.e., Known / yet to be known information). The shared knowledge of the world and of the society in particular is required between the interlocutors for the interpretation of the core meaning of the text. Generally the inscription has the following components: auspicious formula, eulogy (information on the ruling king name, regnal year, genealogy …), details about the donation and the concluding part containing name of the scribe, witness, benediction and imprecation. Each component fits in a formulaic linear order in the textual structure of the inscription. These elements, 3 "The unmarked order of constituents in a sentence is Subject-Object-Verb (SOV) in the Dravidian languages." (Krishnamurthi, Bh. 2003.420). But Zvelebil points out rightly that the basic word order may be subject to variation: "The basic order of surface structures is regularly Subject-Object-verb (if not disturbed by stylistic or emphatic shifts)" (Zvelebil, K. 1997.43).

in turn are placed in correlation with information structure and other contextual considerations. Lambrecht (1994) suggests that the formal structure of sentences is related to the communicative situations in which sentences are used. He states that "this relationship is governed by principles and rules of grammar, in a component called informationstructure. In this information-structure component, propositions, as conceptual representations of states of affaires, undergo pragmatic structuring according to discourse situations in which these states of affaires are to be communicated" (1994:334). The information structure, generally speaking, refers to various ways in which information, including propositional information and real-world knowledge, is linguistically encoded. We will examine below how information is encoded, or packaged, in the 10 th -11 th c. Tamil inscriptions and why certain structures have been be selected to convey a given piece of propositional knowledge.5

II.2. Object Marking in Tamil

In general, it is held both by the traditional and modern Tamil grammars that the accusative marker "ai" is present obligatorily with animate nouns and is not obligatory with inanimate nouns. 6 The case marking of direct objects is typologically one of the major concerns in the theoretical setting of Differential Object Marking (DOM) 7 . A number of studies on Indian languages have shown that several parameters like humanness, definiteness, individuation and affectedness contribute to the marking or non-marking of the direct objects. 8 In the Tamil inscriptions we studied, the accusative case marker is very rarely used. The information structure (IS) is an essential component of sentence grammar, one of the determining factors in the linear ordering of the elements. I will try to demonstrate that pragmatics (information structure) is essential to account for the donated object in inscriptional Tamil.

III. The basic SOV pattern

In our corpus, there are several instances of direct objects occurring with various biactancial verbs. There are two types of direct objects: 1) marked with accusative case and 2) unmarked for accusative. Both types of objects are syntactically similar though they differ from each other semantically and pragmatically. The direct objects are placed before the verb and thus fitting the generally recognized 'unmarked SOV' word order.9

III.1. Accusative marked direct object

As expected the accusative marker occurs with objects referring to animate beings and allows some freeness in the linear ordering, OSV in the following example: This inscription records a deposit of money, the interest of which was to be used for feeding Shaiva saints during the festival days. In 1, the noun 'u ¶aiy¡r' the god, is already introduced in the discourse. This accusative marked noun is the direct object of the predicate 's®vi' to worship.

In the following instance, the accusative case marking on the animate noun (lord) also helps to recover the subject function of the noun heading the relative clause. In this common Dravidian relative strategy, a noun phrase filling any function (subject, object, oblique, etc.) can be extracted from the basic clause and postposed to the relative participle form of the verb (kavitta) without any formal expression of its original function (see below section III).

2) SII.2.34.p143.7 …..de*varaik kavitta …. prabai oº¤u…..

…. Lord.acc cover.rp… aureole one

"one aureole … which covers the Lord…."

This inscription states that the queen had set up a sacred image and records a list of objects offered by her to this sacred image. In 2, the accusative marked noun is the direct object of the predicate 'kavi' to cover, whose subject argument is 'prabai' aureole and has two distinct roles. Syntactically this is the subject argument of the predicate 'kavi'. Pragmatically it has focus role, it is part of a list of objects donated by the queen to the sacred image graciously set up by her.

In our corpus, we noticed a rare occurrence of the accusative case marker with an inanimate noun 3) SII. In examples 1, 2 and 3, the accusative marked objects are grammatical objects but not 'objects of donation' to the actual predicate. These nouns, morphologically and syntactically the direct objects, are placed immediately on the left of the predicate. From discourse point of view, the accusative marked nouns are part of the presupposed clause and serve as scene setting and are pragmatically unmarked. They are the determinants or attributes to the object of donation. For instance note that in 2, the 'aureole' is the object of donation, which is syntactically an extracted argument, and represents the new information in the context of the discourse and pragmatically has a focus relation and is placed after the verb.

III.2. Unmarked direct object

In this section we will examine some direct objects that are not marked in accusative case. In contradistinction to the previous section, all the direct objects discussed below are objects of donation of their governing predicate. This inscription states that as ordered by the king the sacred enclosure was built by the general Sri Krishnan Raman. In 6, 'the sacred enclosure' is at odds both on pragmatic and syntactic grounds. Syntactically, by its position, preceding the verb, it is the direct object, but it is not marked in accusative case. This object is referential and is definite as it is prefixed with the deictic marker i-. But pragmatically, this is not the piece of new information, as it is in anaphoric status because of the deictic morpheme. The anaphoric status of the definite direct object requires it to be [-Focus]. While examining carefully the context of the inscription, the new information is 'the subject', the constructor of the 'sacred enclosure'. In this pragmatically motivated sentence, 'the subject' argument, the new information, is in focus relation and is placed at the right of the predicate, a finite verb in this example.

In 4, 5 and 6 the objects of donation are also the syntactic or grammatical objects but are not marked in accusative case. Each object noun is an argument of a finite verb; is referential and even definite in 6. The objects of donation, despite their blatant syntactic and semantic relations, are not marked in accusative. It may also be noticed that these examples exhibit a consistent semantic order : donatorobject of donationverb of donation, independently of their syntactic encoding (see ex. 6). These examples seem to show that the grammar choose to privilege the pragmatic motivation for structuring the sentence than the syntactic motivation.

III.3. Focussed object

Our main concern in this paper is the place of 'donated objects' in the clause. In the following sentences the 'object of donation' is placed at the end of the clause on the right side of the verb. This pragmatically motivated structure seems to be more frequent than the 'unmarked SOV' order which is almost insignificant in our present corpus. The synctactic device used to achieve this goal is the relativization strategy, which is well known typologically to have affinities with the focus strategy12 .

An additional instance of the predominance of the pragmatic structure is the internal ordering of the focussed elements: the more the information is unpredictable the more it is on the right side of the verb. This inscription states that Malarikesavan offered a spittoon to the image of Ganapathi in the temple of Sri Rajarajeshvara. It is inferable from the context that some object would be gifted to the statue but less likely inferable is the identity, quantity and weight of the object. The focus part of the sentence contains the identity, the quantity and the weight of the donated object. This constitutes the new information which is naturally in the focus part of the sentence. The noun phrase 'pa ¶ikkam' with the numeral quantifier is the right dislocated object of donation. The pragmatics triggers also dislocation of the quantifiers, which follows the noun head. "one solid image of Maha Vishnu, having four divine arms (and measuring), nineteen viral and six torai in height from the feet to the head, was set up"

This inscription states that the king had graciously set up a copper image along with many objects as attributes and gifts and all these objects were measured and engraved on stone. Example 9 follows immediately the introductory statement. The first part of this sentence which precedes the verb gives the technical description of the gifted image, which is contextually in the domain of shared knowledge, serves as a scene setting topic for the new piece of information, the object of donation. 13 The focus part consists of two new pieces of information: the identity and the quantity of the statue. 'The queen Sinnavai gave sixty kasus (money) for one perpetual lamp she had given.'

In this inscription a series of two gifts (lamps and money for their maintenance) made by two women to the god of Tiruamali are recorded. Example 11 is about the second gift of the series, made by the queen Sinnavai of a perpetual lamp and an amount of money (60 kasus) for the maintenance of the lamp. Both events are structured in a sequential order. In each clause the referent of the gift, lamp and money, is inferable from the context. But the quantity of gifted object, being the new information, is in focus position respectively. Like in 8, the lamp is part of the two clauses with different roles in each case.

11. SII. In sentences concerning statues and other sacred images that were set up as gifts, there are two distinct information units. The first part contains all technical iconographic descriptions (height, weight, the metal in which the statue is made of, and whether the statue is hollow or solid etc.). The second part, the focus part, gives the new information -the identity (name) of the image and the quantity-. In an inscription (SII.2.29) there are 13 gifted objects of which the description follows the above type and this pattern seems to be followed as a norm. How ever, a complete statistical analysis is needed before generalising this hypothesis.

we have given eleven veli of land as tax free …to (the image of the goddess) ulakmu«utum u ¶aiyanacciyar that we have graciously set up in this temple… This inscription records that the king had set up an image of a goddess and that he had offered to the goddess eleven veli of land as gift. In 12, we notice two clauses, in a sequential order with two different structures. In the first sentence, the image of the goddess, an object of donation, is in focus relation, which shows a pragmatically motivated structure. But the second sentence has an 'unmarked SOV' ordering of constituent and the gifted land, object of donation, is also in the grammatical position of the object of the verb. This type of mixed structure, though rarely noticed, comes as a proof of the different structural possibilities available to the grammar of the Tamil inscriptional language.

Examples 8, 10 and 11 show the multilevel interaction of the information structure in the patterning of the texts. At the clause level, the relativization strategy is used to focus the object of donation in each part of the sentence and the repetition of the relative participle vaitta 'put' in 8 clearly emphasizes this structural symmetry. On the sentence level in these examples, the linear order of the clauses and the dative case marking on the first clause signal the overall topicfocus relationship that links the two clauses.

A finer use of the information structure is also observable. In examples 7 to 12 different types of objectsmoney, land, sheep, sacred statue, vessel and other decorative objects-are noticed as gifts or offerings. All the sentences have a two place verbs and in each sentence the semantic patient/object role is saturated. In all the above sentences, except one instance (example 12), the object of donation is extracted from its basic position and dislocated on the right side of the verb. This structural position corresponds to the focus position. Rather, the new information, or more precisely, the more unpredictable information is placed at the right most part of the sentence. The right dislocation of the object of donation is in correlation with the inversion of numeral quantifiers. Instead of a binary distinction of predictability (predictableunpredictable) a scalar notion of predictability is in corollary with the phenomenon of quantifier floating (examples 10 & 11).

Conclusion

In this brief survey we tried to show that the placement of the objects of donation is related to their informational status. In spite of the fact that the accusative marking does exist as a specific marker of direct object (ex. 1 to 3), it seems to be never used for the introduction of the objects of donation in these inscriptional texts. The objects of donation appear into two structures: 1) An 'unmarked (SOV)' constituent order as illustrated by examples 4 to 6 where they are not marked in accusative case, even when definite (ex.6), but where the linear order of presentation matches the semantic sequence: donatorobject of donation . 2) A pragmatically motivated word order, where the object of donation is dislocated on the right side of the verb, consistently put in a focus position, examples 7 to 12. In this case, the link between the object of donation and the focal position is maintained whatever are the grammatical relations and the overall structure of the sentence. All these evidences plead for a thorough and distinct analysis of the grammatical relations and the discourse structure of the texts. Detailed investigations are needed to expound more clearly the relation

  The village has already been mentioned in the text and is established as topic of the clause. The noun £r 'village' marked in accusative prefixed with the deictic particle is an argument of the two place predicate £ ¶a¤u 'pass across'. This noun is in fact the definite direct object and form part of the discourse narration, and can be considered as backgrounded event. This clause is subsidiary or a framework to the propositional content 'canal which irrigates the other villages' expressed in the main clause. The noun phrase 'v¡ykk¡l' chanal, is the subject argument of two verbs 'cross through' and 'irrigate' respectively. The object 'ivv£rai', though referring to a direct object is not the complement of a verb expressing a donation.

	2.5.p56.11
	…..ivv£rai	£ ¶a¤uttup po*y pu¤av£rkkup	p¡yum	v¡ykk¡l …..
	…..deic.village.acc cross.go.adp	other villages.dat irrigate.rp channel
	'… channel which crosses through the village and irrigates other village…'
	Example 3 comes from an inscription describing the donation of rice fields from
	different villages.

  This inscription records that the king gave 11 veli of land, exempted from tax, to the goddess that he had graciously set up in the Rajarajisvaram temple. In 4 we have an 'unmarked' 'SOV' order of constituents which is not frequent in inscriptions. 11 This 'unmarked order' shows no pragmatic function. The sentence contains a finite verb and shows agreement with the subject argument. This inscription describes a gift of land, to the God of the Tirukkadalmallai village, made by the members of the village assembly. As in 4, we have an 'unmarked SOV' constituent order. But in 5 we notice the inversion of the numeral quantifiers, 5 and 200 respectively, at the level of the noun phrases, thus giving rise to the phenomenon of quantifier floating.

	6) SII.2.31.p139.8-20
	u ¶aiy¡r ¿rir¡jr¡jad®var	tiruv¡ymo«intaru½a	ittiruccu¤¤um¡½ikai
	lord	PN	sacred.order.grace.inf.	deic.sacred enclosue
	e ¶uppitt¡º		s®n¡pati […] ¿ri kri¿¸an r¡maº…
	construct.caus.past.3.m.s		General	[…] PN….
	'(as) the king Sri Rajarajadeva has graciously ordered, the general (…) Sri Krishnan
	Raman (caused to) construct this sacred surrounding palace'
	4) SII.2.61.p246. 3-6
	… n¡m [….] … [….] patiºoru v®li	nilam	i¤aiyiliy¡ka […] ku ¶utt°m….
	…. 1.pl	11	veli.unm land	tax-free	give.past.1pl
	'we gave 11 velis of land as tax free ….'
	5) SII.1.42.p68.3-19
	mah¡sabaiyo*m […. ] ta ¶i 5º¡l	ku«i 200		iºº¡yaº¡rkku […..] ku ¶utto*m….
	great assembly.1.pl […] land 5.inst	kuzi.unm 200	deic.Godd.dat […] give.past.1.pl
	"we members of the great assembly…. gave… to the God 200 kuzi consisting of 5 rice
	fields'

  7. SII.2.36.p149.2-3 ….. m¡lari ke*savaº [….] ku ¶utta pa ¶ikkam o¸¤u ni¤ai a¤upattoºpatiº palam…..

	…….PN	[….] give.rp spittoon	one weight 69	palam.unm
	'Malari kesvan gave [….] one spittoon, which weighs sixty-nine palams'

  In the second clause, the object of donation '96 sheep' constitutes the new information and is the focus of the clause. Right dislocation of the donated object goes in symmetry with the floating of quantifier. The numeral quantifier is on the right side of the noun it qualifies instead of preceding it.

	8. SII.13.63.p29.8-10
	c°«a mil¡ ¶u ¶aiy¡º vaitta nunt¡vi½akku oº¤ukku vaitta ¡ ¶u to¸¸£¤¤¡¤u…
	PN	put.rp	perpetual lamp one.dat	put.rp sheep 96
	9. SII.2.52.p217.12-20
	p¡t¡dik®¿¡ntam pattonpatu viraley ¡ru torai usarattu	n¡lu srihastam
	foot.from-head.end 19	viral	6	torai	height.obl	4	sacred.arm
	u ¶aiyar¡kak kanam¡ka eluntaru½ivitta	mah¡viá¸ukka½ tirum®ni	oruvar
	possesseur.as solid.aaka	erect.be gracious.rp Mahavishnu.h	sacred.statue one-m.s.h

"Solamilatudaiyan had given 96 sheep for (burning) a perpetual lamp he had bestowed" This inscription records a gift of 96 sheep for burning a perpetual lamp. In 8, there are two clauses which are arranged in a sequential order. First, Solamilatudaiyan gave a perpetual lamp, and second, for this perpetual lamp he offered 96 sheep. The perpetual lamp is part of the two clauses. In the first event, an object of donation, it is in focus relation. In the second event, a beneficiary marked in dative case, it is in topic relation.

  10. SII.1.68.p101 … si¸¸avaiyar [….] vaitta nand¡vi½akk.oº¤u.kku ku ¶utta k¡su a¤upatu.

	…. NP….	give.rp perpetual lamp. one.dat give.rp kasu	60

  This inscription records the gift of 180 sheep, the ghee obtained from these sheep should be used to keep alight two perpetual lamps. The two perpetual lamps, present already in the discourse context and constitute the known information, are in topic relation. Note the contrast between the topic noun phrase where the numeral quantifier precedes the noun and the focus structure where the noun precedes the numeral quantifier. This example strengthens our hypotheses that the quantifier floating is one of the features of the focus part of the sentence.

		1. 83. p114-115
	…ira¸ ¶u nond¡vi½akku …. erippata¤ku ca¸ ¶apar¡kkiramavirar vaitta c¡v¡
	…2	perpetual lamp	burn.vn.dat PN	give.rp die.neg
	m£v¡	p®r¡ ¶u	n£¤¤e¸patu
	age.neg big sheep 180
	'in order to keep two perpetual lamps burning, Chandaparakkirama Vira gave one
	hundred and eighty deathless and ageless big sheep (i.e. the total number of sheep
	remains unchanged)'.
	12. SII.2.61. p246.3-6 (cf. 4)
	…	[….] ikkoyilil	n¡m e«untaru½ivitta	ulakmu«utum u ¶aiyan¡cciy¡rkku [….]
	….	[….] deic.temple.loc 1.pl	erect.grace.rp	PN.dat
	patiºoru v®li	nilam i¤aiyiliy¡ka […]	ku ¶utt°m….
	11	veli.unm land	tax free.as […]	give.past.1.pl…
	13

It is a great honour and pleasure to be able to contribute to this volume in honour of Professor S.V. Shanmugam. It is also a pleasure to acknowledge my immense gratitude for all I have learnt from him in linguistics and beyond.

I am indebted to Christian Pilot-Raichoor for many discussions and comments on various drafts during the course of writing this paper. My special thanks to Corinna Anderson for her comments and suggestions on an earlier draft.

It is important to note that in the Tamil inscriptions the accusative, the genitive and the locative are very rarely used. But the only case widely is used the dative. This shows very clearly that the word order variation is not due to rich morphological case system.

Discussions about the distribution of information in clauses and sentences can be traced out in the works "Functional sentence perspectives" elaborated by the Prague school linguists in the 1920's and in more recent works like[START_REF] Halliday | Language structure and language function[END_REF]Halliday ( , 1984)),[START_REF] Lambrecht | Information Structure and Sentence form: Topic focus and the mental representations of discourse referents[END_REF].

However,, the objects that are weighed, measured, counted, received take the accusative case marker.

Lazard 2001

[START_REF] Masica | Identified Object Marking in: Hindi and other Languages[END_REF][START_REF] Murugaiyan | Marquage diiférentiel de l'objet et variation actancielle en tamoul[END_REF][START_REF] Pilot-Raichoor | L'objet en badaga[END_REF]

The view mentioned in previous studies that SOV is the unmarked word order, is assumed in this study. But this order does not reflect the real situation in the language of Tamil inscriptions and it is dubious to say which is the marked or the unmarked word order at this stage.

The reference of the examples follow the following pattern: SII.2.5.p56.11 = South Indian Inscriptions, followed by the number of the volume, followed by the number of inscription, followed by page number(s) and finally the number of line(s). Each part is separated by dot.

The 'SOV -unmarked' order is one of the possibilities used in the inscriptions. The variation in constituent order seems to be a common feature in the language of inscriptions[START_REF] Gai | Historical grammar of Kannada[END_REF]., Sekhar, A. C. 1953[START_REF] Murugaiyan | Organisation prédicative dans des textes épigraphiques tamouls[END_REF]

Croft 2003: 108-109.

between information structure and syntax in the early Tamil epigraphic texts, however we hope this contribution may point the way to further analysis in this area of historical linguistics.

Abbreviations:

Zvelebil, K. 1970

The language of earliest Tamil inscriptions. In: Kamil Zvelebil et Jaroslav Vacek, Introduction to the historical grammar of the Tamil language; pp 9-103. Publishing House of the Czechoslavak Academy of Sciences, Prague.


Alejandro Lobo Guerrero

An Informed Synchronization Scheme for Audio Data Hiding

Keywords: Audio Data Hiding, Informed Synchronization, Spread Spectrum

This paper deals with the problem of synchronization in the particular case of audio data hiding. In this kind of application the goal is to increase the information of an audio data set by inserting an imperceptible message. An innovating synchronization scheme that uses informed coding theory is proposed. The goal is to realize a complementary approach from two different techniques in order to obtain an enhanced synchronization system. To that end, the analysis of the classical spread spectrum synchronization is done and this classical scheme is improved by the use of side information. Informed coding theory is presented and revisited taking into account the problem of synchronization to enable the selection of signal realizations called Feature Time Points (FTP) which are correlated with a code. Such considerations yield to the definition of informed synchronization. The proposed scheme and the definition of FTP are after presented taking into account the robustness criterion. Finally, results and comparison with classical spread spectrum synchronization schemes are presented.

INTRODUCTION

Audio data hiding [START_REF] Boney | Digital watermarks for audio[END_REF][START_REF] Loboguerrero | Iterative infirmed audio data hiding scheme using optimal filter[END_REF] is a method that allows the insertion of an imperceptible mark in a signal data set. Although this technique is mainly used to guarantee intellectual property, applications in different areas are constantly been developed. This is the case of data hiding for data transmission. Several applications are possible in this particular context. For example, if the priority information which is transmitted is the speech voice, then it may be useful to transmit video analysis information such as lips moving parameters, the speaker's face or any other information identifying the speaking face. Such an application is addressed in the project ARTUS ℵ which aims to embed animation parameters into audio and video contents. When implementing audio data hiding schemes the designer has to take into account not only coding but also synchronizations constraints. Theses constraints are:

-Minimum acquisition delay and complexity: The procession time devoted for the synchronization task is wasted and con not to be used for decoding the hidden message; -Temporal derive management: due to D/A A/D conversions, the global system has to cope with re-sampling and temporal derive; -Robustness to noise and compression: those processes are part of the transmission channel; -Minimal audible distortion: the hidden information has to remain unnoticeable; -Maximal transmission rate of the inserted message: the capacity of the scheme has to be as important as possible.

Watermarking synchronization for audio is classically achieved using spread spectrum (S.S.) synchronization theory 3 or audio characteristics as a beat [START_REF]Digital communications[END_REF] . In this article the S.S. approach is completed by informed embedding analysis yielding -Kirovsky and Malvar have proposed an audio watermarking scheme that uses audio analysis for extracting instants that enable synchronization and avoid security issues inherent with classical spread spectrum synchronization techniques [START_REF]Digital communications[END_REF] . The synchronization scheme is based on beat detection of musical contents that lead to a natural cutting of temporal axis. The proposed algorithm first estimates the mean length of the beat and secondly estimates the exact occurrence of each beat. The audio signal is then after time-warped in such a way that the period between each beat remains constant and equal to the length of message code. The signal is after watermarked using a classical spread spectrum scheme and an inverse warping is also performed. Such an scheme is robust to time-warping attack and time translation but is not suitable for signals that did not contains beats such as speech signals.

-Haistma et al. have presented an audio watermarking scheme that uses a modified correlation function to decode the mark and enable synchronization [START_REF] Jaap Haitsma | Audio watermarking for monitoring and copy protection[END_REF] . The matching function, called SPOMF for Symmetrical Phase only Matched Filtering, is performed in the Fourier domain and the translation recovery is done calculating: The use of phase information improve the reliability of the detection of the synchronization peak (if S 1 (t)=S 2 (t-τ)) the Corr p (S1,S2)=δ(t)). The behavior if this system will be studied and compared with the proposed scheme in the section devoted to results.

( )         = - ) ( ) ( ) ( ) ( 2 1 2 1 1 2 1
The following sections present the main synchronization scheme that is used in audio data-hiding and the concepts of the informed theory. This will establish the context to introduce the informed synchronization scheme. The related advantages and disadvantages are outlined.

FROM SPREAD SPECTRUM SYNCHRONIZATION TO INFORMED SYNCHRONIZATION

The present work is related to two different approaches which are presented and the advantages and disadvantages are outlined. The goal is to develop a scheme that aims to profit from the best characteristics reducing the inconvenients of each one. Theses approaches are the Spread Spectrum and Informed approaches.

Classical Spread Spectrum Approach

One of the most popular synchronization system in the field of telecommunication is based on the classical Spread Spectrum theory 3 . This system uses a specific code (a pseudo random signal) for guaranteeing synchronization. This code is added to the host signal in the transmission stage. The synchronization at the receiver may be implemented by using an sliding correlator matched with the received code. Then, the resulting signal is

(1) { } ) ( ) ( ) ( ) ( * m n c n Ac n s n y - ⊗ + =
Where s(n) represents the host audio signal, c(n) the inserted code which power is determined by the coefficient A. C(n) is a white code and by consequence its autocorrelation is ideally an unit impulse. The idea is then to detect the presence of this peak by computing the correlation between the received code and a local copy. The correlator output is then compared with a threshold to determine the phase of the received synchronization code. Note that when using this technique in audio data-hiding applications the host signal s(n) is treated as a "noise" and consequently the presence of s(n) perturbs the detection of the peak (figure No. 1).

Figure 1. Classical Spread Spectrum Synchronization

When the SNR is not large enough (e.g. the power of the code is too weak), the localization of the peak may fail because the intercorrelation between the code and the host signal is too important. In this case, before evaluating the threshold, a supplementary filter can be applied to reduce the noise perturbation. One classical solution to solve this drawback is to combine the use of a periodic code and an average filter. This average filter a(n) is expressed by the next equation:

∑ = = K k k n r K n w 0 ) ( 1 ) ( (2)
In this filter, the received signal r(n) (host signal, codes and channel noise) has been divide in blocks noted with the sub index k. The number of averaged blocks is determined by the constant K. This filter represents an average system that aims to reduce the noise effect (this is composed by s(n) plus channel noise). The signal y(n) is then expressed as:

(3) ) ( ) ( ) ( * M n c n w n y - ⊗ = Replacing w(n) as in equation 2, r k (n) by s(n)+n(n) and regrouping, it follows: [ ] { } ) ( ) ( ) ( ) ( ) ( ) ( * 0 * M n c n n n s K A M n c n c K A n y k k K k k - ⊗ + +       - ⊗ = ∑ ∑ = (4)
Ideally, when K tends towards infinity the effect of the noise perturbing signals s(n) and n(n) will be reduced and the codes autocorrelation will be preserved.

Such a synchronization process leads to several disadvantages when applied to audio data hiding. A spread spectrum based synchronization is defined by 3 different parameters that will enable to improve the detection step: 1. To increase the power of the inserted codes (A in equation 4); 2. To increase the length codes (M in equation 1); 3. To increase K (in equation 4).

Nevertheless, each one of these strategies presents important drawbacks. Strategy 1 is often discarded because of the high probability of adding audible distortion. In fact, the constraint of inaudibility imposes a very weak SNR. The second and third options imply main disadvantages:

-Important acquisition delays; -Unsuitable in presence of temporal clock derive.

We propose in this paper to use informed coding theory to improve the above issues. In the following, the principles of this technique are introduced and the new informed synchronization scheme is proposed.

Informed Synchronization Approach

In this section, the main concepts of the informed theory are introduced including definition, robust synchronization and a more general presentation of informed synchronization.

Definition

General informed coding theory [START_REF] Cox | Watermarking as communications with side information[END_REF] proposes to use the knowledge of the host signal in the transmission stage (so it is no longer treated as a random signal but as a deterministic one) to select optimal codes. Basically, using side-information for coding enables a reduction of the embedding power while it is possible to achieve the same performance in term of robustness. In this kind of analysis, the host signal and the code are often represented as vectors. Informed coding is then equivalent to select a codeword from a codebook representing the code-word that is the nearest + to the host vector. Such techniques first presented by Costa 7 , and used in the field of image watermarking by several authors [START_REF] Miller | Informed embedding : Exploiting image and detector information during watermarking insertion[END_REF][START_REF] Le Guelvouit | Perceptual watermarking of non i.i.d signals based on wide spread spectrum using side information[END_REF] , lead to an increasing of the capacity while preserving the robustness Informed synchronization can be seen as an analogous strategy where the goal is to select signal vectors that are the nearest to one codeword. The selected host vectors denoted in this paper by Feature Time Points (FTP's) will be used for synchronization purposes (see section 4). Thus, Informed synchronization can be seen as an extension of synchronization techniques which relies on the content of the host signal to provide invariant feature points or areas. Moreover, as it is addressed further in the paper, the use of informed theory enable to improve the robustness of the scheme to synchronization processes compared with classical S.S. techniques.

Figure 2 presents the geometrical interpretation of informed synchronization an is compared with a classical S.S. synchronization scheme. The vertical axis represents the linear correlation between the host vector s(t) and the codeword c. The horizontal axis represents the temporal axis, it is equivalent in the informed coding paradigm with the index of the codebook. In this correlation/temporal plan, different realizations of the host signal are represented by crosses. In (a), the arrows represent the effect in a classical S.S. scheme of a constant embedding power. In this case, the code word is added on each host vector to create a synchronized signal and the coding of the synchronization information does not depend on the host signal. Ideally, in absence of the host signal, the effect of the added codes yields a correct detection where all synchronization points are over a predefined threshold (denoted with a gray region). When the host signal is present, the resulting marked signals may all lead to present a significant correlation ¡ : this is why classical S.S. synchronization averages vectors before computing linear correlation.

In (b), the figure illustrates the effect of informed synchronization which can also be seen as feature detection: only the most highly correlated vectors are dept for synchronization purposes (noted with dark crosses). They represent singular points such as local maximum of the correlation considering a temporal neighboring window V i (t) (cf. S(t 1 ) and S(t 2 )). It is important to note in this case that the synchronization can be achieved without altering the original signal (no distortion introduced) following the condition that the robustness is not guaranteed. The extraction of FTP's will be described further in this paper: the main idea is to implement an invariant time filtering system. Message coding is achieved by adding the message codes in the instants corresponding to the Feature Time Points. In reception stage, the message will be decoded accordingly with the instants determined by a local copy of the feature time detector.

Controlled Robustness Informed Synchronization

Because considering noise in the model enables to deal with robustness, this perturbation has been taken into account to lead to a Controlled Robustness Synchronization Scheme. The principle of controlled robustness is depicted on figure 3.: The chosen maximums of the correlation (FTP's) can be modified to bring these points farther from the other points in the window neighborhood V i (t) (cf. S(t 1 ) and S(t 2 )). This operation will increase the probability that a local maxim is preserved in noise presence. Controlled Robust Synchronization can be also used when there is not FTP's detected over the host signal (e.g. the host signal power is very weak). In this case, one point (vector) of the host signal can be modified in such a way that the correlation is reinforced and it becomes an FTP's. It means that a FTP is forced (cd S(t3)). From a vector point of view, this means that a chosen vector is modified by an addition of a from a code vector to transform it into a FTP. The robustness is represented by the distance from the FTP to the nearest vector and is function of the probability of missing or creating a new FTP. In the previous section the informed synchronization has been presented from a vector point of view where the selection of the closest pair (host vector, codeword) is done only considering a set of different host vectors. Nevertheless, the theory of informed coding can be extended by using a codebook, of several code words that will permit to reduce the distance between a host vector and a code word. In this context, the synchronization has to deal with to different codebooks. The first is provided by the host signal, the second is a predefined codebook. Figure 4 illustrates the representation of a general informed synchronization scheme . In this case, four code words have been used and a normalized correlation is computed to lead to a detection region representing a cone [START_REF] Cox | Digital Watermarking[END_REF] . Note that if on one hand, an important codebook will lead to a statistical good matching between the code word and the host signal, on the other hand, the complexity of such a scheme will be multiplied by the number of code words present in the codebook ß .

General Informed Synchronization

PROPOSED SYNCHRONIZATION SYSTEM

Once the classic synchronization systems and the basis of informed embedding have been introduced, an implementation of such a system is proposed. This synchronization system has been developed taking into account the main advantages of the S.S. and informed systems and looking for minimizing the existing disadvantages. Such an scheme must fulfill few requirements:

-Informed System: s(n) is not analyzed as a noise; -Detection of FTP's should be a simple process; -FTP's must avoid time overlapping of consecutive message codes: A minimum time separation is required; -The system must not include important average delays; -The system has to integrate a noise robustness control system. -The acoustic distortion must be taken into account.

The figure 5 shows the proposed informed synchronization scheme. This system is composed by three stages. In the transmission stage, a feature instants detector analyses the host signal s(n) in order to find and reinforce FTP's. How the FTP's are defined and reinforced is presented in section 4.1.

ß This is present just as a theoretical approach. In the present work, only one code has been used. Future developments will be focused to the usage of a codebook. The channel noise can be modeled from two points of view:

-Additive White Gaussian Noise (AWGN): A A/D D/A conversion can be done in order to transmit the signal through an analog channel. In this case, AWGN will model the introduced perturbation; -Compression with lost: the most usual compression format is MP3. In this case the channel perturbation can be studied as a low pass filter followed by an additive compression noise (caused by a re-quantification system).

The detection stage, is analog to the transmission stage. The receptor has to apply the feature detector over the received signal and decode the message. For taking into account the eventual presence of noise, the decision criteria has to be defined. In the following sections a detailed description of the reception stage and detection criteria will be presented.

Emission Stage

Feature Time Points Definition

Following the ideas exposed in 3.2.1., it is possible to define FTP's and to implement the corresponding detector. FTP's have to match several conditions. They have to be easy to detect, robust to the channel and compression noise and two successive FTP's have to be separated (in the time axis) by a minimal distance. Two different filters have been chosen to deerminate FTP's and to fulfill these conditions. They are hc(n) and mm(n). The first one of the two filters (hc(n)) must be chosen agreeing the following criterions:

-To bring out some characteristic of the signal; -To be robust to channel and compression noise.

As a synchronization charateristic, it could be natural to consider the maximums over the host signal. In analogous way, the maximums over a pass band or low pass filtered version of s(n) could be used as a synchronization criteria (future works will be developed in this line). However, the most of them lack of a suitable noise behavior. In order to have a filter which behavior allows a gain in the SNR, the S.S. theory provides the necessary tools. In fact, the use of a filter matched to a pseudo random code will optimize the SNR and will yield a robust behavior face to the channel noise. Then, the filter hc(n) is defined as

) ( ) ( * M n c n h c - = (5)
Where c(n-M) is the pseudo random code with length M. If the maximums of the filtered signal are taken to realize synchronization, an enhanced behavior concerning the noise will e provided by the system.

Nevertheless, the criteria has to match a supplementary condition. Since each FTP in s(t) will denote the origin of a message code and since overlapping of those message codes is not suitable, the FTP's must have a minimal distance separation equal to the codes length (this is also important when improving robustness by synchronism codes addition as is explained in deep in section 4.1.2.). Although choosing the maximums of s(n) filtered by h c (n) makes the system robust, this choice dos not answer to the minimum distance exigencies. This is why a second filter (mm(n)) is proposed. The idea is to analyze the signal over limited duration segments (equal to the code length) and to define the local maximum of each segment as a FTP. This choice will guarantee the minimal required separation. This yields to a morpho-mathematical filter defined by the following equation:

[ ] [ ] )) 1 ( ( ),..., 2 ( ), 1 ( ), ( max ) ( ) ( - - - - = = N n y n y n y n y n y nm n m (6)
This filter determines the local maximum over a N samples window in signal y(n). The window size N is chosen to be equal to the length code M and thereby to avoid overlapping between codes. The resulting signal m(n) is a stair-shape signal. The maximums of the doubled filtered signal m(n) are useful for synchronization proposals and can be visually noted as "flat" segments. However, these flat segments are spread over several samples whereas the synchronization instants must be defined over just one sample. In order to define the synchronism instant on just one sample, a particular instant No must be associated to this flat segment of signal m(n). N 0 is therefore defined as the first sample in the flat segment. Figure 6 depicts the process. In (a), the intercorrelation between a realization of s(n) and c(n-M) is illustrated. The circles show how when using the maximums of this signal as synchronization points often generates points that are too close in time. In (b), the local maxim has been taken and the stair-shape signal is visualized. In this case, the circles denote two flat segments corresponding to the local maximums of this signal that are easily detectable. The vertical line shows how these segments are associated to singular sample points defining in this way N 0 . Note that two consecutive instants N 0 are always separated by a distance at least greater than M allowing the insertion of consecutive codes without generating overlapping between them. This instants (N 0 ) are determined by the application of a suite of time invariant causal filters (hc(n) and mm(n)). This characteristic allows to relate N 0 to an instan over s(n). In fact, if the delay produced by hc(n) is N c and N m that one introduced by mm(n), the instant associated to N 0 (called Feature Time Point) over s(n) is:

) ( 0 m C N N N FTP + - = (7)
It is important to note that the chosen filter h c (n) is exactly the same as used in S.S. systems. This bring a SNR gain face to the channel noise. However, s(n) is not treated in the same way then the channel noise. To use s(n) as a known signal has permitted the definition of the FTP's as the maximum of the correlation between s(n) and c(n). From an informed point of view, this filtering system allows the selection of the signal vectors having a maximum of similarity compared with the pseudo random code in a determined period of time. In the next section, the way to increase or control the system robustness by codes addition is explained.

Controlled Robustness Informed Synchronization

The filter hc(n) has the suitable properties face to an additive noise. However,, the interest is focused in controlling the robustness of the system (as enunciated in section 3.2.2.). Once the analyze of the host signal is done and the feature instants are determined, the idea is to reinforce the maximum found in equation 6 by adding a synchronism code equal to the filter impulse response of hc(n) (this is illustrated in figure 5 by a switching system controlled by the FTP's detector). Such an addition yields to interesting perceptual properties because a code will be added in a zone of the host signal that present high correlations and consequently are similar. The synchronism code position is chosen to respect the causality constraints of the system. If the origin of the code is place in the instant FTP the impulsion yield by the correlation will be placed in No reinforcing the maximum found in equation 6. There is only two possibilities for each instant in s(n). From a communications point of view, it is possible to associate one hypothesis Ho and H1 as follows:

-

H 0 : x(n) = s(n) if n is not FTP, -H 1 : x(n) = s(n) + Ac(n-FTP) if n is FTP,
When applied to the filter hc(n), it implies that: -

H 0 : y(n) = s(n)⊗h c (n), -H 1 : y(n) = s(n) ⊗ h c (n) + Ac(n-p) ⊗ h c (n)
When the morpho-mathematical filter is applied it follows:

-H 0 : m(n) =mm[y(n)=s(n) ⊗ h c (n)], -H 1 : m(n) =mm [y(n)=s(n) ⊗ h c (n) + Ac(n-p) ⊗ h c (n)]
We note ∆ the term Ac(n-p) ⊗ hc(n). Its importance lies in the fact that the amplitude on the peak present in a feature instant is directly controllable by adding a code weighted by the constant A. Furthermore, the value ∆ will determine the robustness degree of the system (The effect of this operation is illustrated in figure 6(b) by the pointed lines). It is also important to note the choice of the filter hc(n) combined with the use of s(n) is equivalent to an informed synchronization scheme in which the maximums of the autocorrelation of the synchronism codes are placed on the local maximums of the inter-correlation between c(n) and s(n). From an informed point of view, a vector addition is realized in the FTP's to bring them more easily detectable.

Reception Stage

The same filters hc(n) and mm(n) are used in this stage. However, the noise introduced by the channel must be taken into account to define the detection criteria. This criteria is presented in the following subsection.

Detection Criteria

Although the FTP's have been defined as the maximum of the correlation between the host signal and the code, the channel noise influence in the reception stage makes this criterion insufficient. The presence of noise could generate peaks (even if they are often weak they are still maximums) that prevent detection. To face this problem, a comparison with a threshold must be defined. The first task for the detector is to look for a flat shape segment in m b (n). Once the flat-shape segment has been identified the system must apply a criterion to determine if this point corresponds to H1. If the criterion is not accomplished, the system will decide H0. To define the criterion, a threshold is defined from the two established hypothesis. Based on the fact that the difference between H0 and H1 for a specified instant n is ∆, it is known that the minimal difference between a reinforced and a non reinforced point is ∆. The idea is to compare this difference (to do this the analyzed sample and its closest neighborhood are taken) to a predefined threshold. The criterion is:

(8) (9) decided H n m n m if b b 0 ) 1 ( ) ( ⇒ < - - η decided H n m n m if b b 1 ) 1 ( ) ( ⇒ > - - η
It means that it compares the first sample of mb(N 0 ) in a found flat-shape with its immediately precedent neighborhood. To determine if this point corresponds to a FTP the threshold is applied allowing the system to decide between hypothesis H 0 and H 1 .

It is important to note that the threshold depends of the codes amplitude A. For the correct behavior of the system, this value has to be fixed and known in reception.

RESULTS

The tests have been realized over a digitally recorded sample of an audio broadcasting program sampled to 44.1 kHz (CD quality). The total number of samples is 5120000. The audio file includes speech, music, different kinds of isolated and mixed sounds. The idea is to compare the behavior of the proposed system and a classical S.S. synchronization system over an analogical AWGN channel. In both cases the power of the synchronism has been fixed to the same value. It means that they have the same length N (fixed to 512 samples) and the same amplitude A. This power has been fixed following an audibility criterion: it is the maximum possible power that does not include an audible distortion. Although a young listener has been used to establish this value, the results remains subjective. To deeply evaluate the subjective distortion, more tests more tests should be practiced. For the S.S. system, the K value has been defined (for the average system) as: K=100. For simulating an analogical transmission, a delay non multiple of the sampling frequency is used. This is equivalent to realize a A/D D/A conversion. Then, the number of errors has been computed for different SNR's including an ideal noiseless channel. In a second test, the behavior of the system concerning the mp3 compression is analyzed. The same audio file then in the first test have been taken. For each used bit rate, the file has been compressed and immediately decompressed. The detection are realized over the decompressed signals. Five bit rates have been used for this test, varying from 96 to 224 Kilobits par second in steps of 32 kbps. The results are depicted in figure 7. The results verifies the fact that a S.S. system treats the host signal as a noise. From an ideal noiseless channel, the power of the host signal perturbs the detection generation an important number of errors. For the informed scheme in the same conditions, the send and received signal are equal and any perturbing noise is added. The consequence is a perfect (zero errors) detection. By the other hand, when SNR is decreased, the S.S. system presents little variations in the number of errors compared with the informed scheme. This can be explained by the fact that the channel noise contribution to the total perturbing signal is little comparatively speaking. In fact, the channel noise is treated jointly with the host signal and its effect is minimized by the average filter. It is also important to note that on one hand, the S.S. and the SPOM (cf. section 2) filter presents improving results compared with the classical S.S. system for RSB under approximately 46 dB's concerning BER. For this test the SPOM filter has not an average filter applied and by consequence it does not generate important delays. However, complementing the SPOM system with an average system yields important improvements. In (b) the results about MP3 compression are depicted. In these tests, the system did not generate errors for debits over 224 kbps ( compression rate approximately equal to 3:1).

CONCLUDING REMARKS AND FUTURE WORKS

Synchronization in data hiding systems used for data communications is a challenging problem. An informed spread spectrum system presents an innovating solution. When using a pseudo random code to determine the synchronization instants and analyzing the host signal not as a noise, this solution allows high robustness and controlled audio distortion. In this work, just one pseudo random code has been used. However, a codebook containing several codes of many kinds can be used to accomplish this task, future work will be developed in this direction.

Figure 2 .

 2 Figure 2. Geometrical comparison of classical and informed synchronization schemes.

Figure 3 .

 3 Figure 3. Controlled Robustness Informed Synchronization scheme.

Figure 4 .

 4 Figure 4. General informed synchronization scheme.

Figure 5 .

 5 Figure 5. Proposed Informed Synchronization scheme.

  (a):Intercorrelation between S(n) and H c (n) (b): Morphomatematical Filtering

Figure 6 .

 6 Figure 6. Filtering effect for h c (n) and mm(n)

Figure 7 .

 7 Figure 7. Comparative Results with the same power embedding

funded by French RNRT Artus Project


P Bas

B Macq

A NEW VIDEO-OBJECT WATERMARKING SCHEME ROBUST TO OBJECT MANIPULATION

This paper presents a watermarking scheme for image or video objects. The watermarking of video objects implies different constraints from raw watermarking methods. The mark has to be detected after object manipulations such as rotations, translations and VOL modifications. To achieve these requirements, the embedding scheme exploits the shape of the object: a random sequence is transformed to fit the scale and the orientation of the object. The detection of the mark is performed applying an inverse transform and calculating a correlation between the random sequence and the warped object. Our results illustrate the fact that the presented method is robust to object manipulation.

INTRODUCTION

With the emergence of new multimedia standards such as Mpeg-4 and Jpeg-2000, the notion of video-object or imageobject is more and more widespread [START_REF] Ebrahimi | Mpeg-4 natural video coding -an overview[END_REF]. Consequently, a need to protect the different objects of an image or a video appeared. The watermarking technologies enable the embedding of an unnoticeable and indelible mark inside multimedia contents such as images, video or audio [START_REF] Hartung | Multimedia watermarking techniques[END_REF]. It appears that the new multimedia standards are strongly bounded with watermarking methods. For example, the Mpeg-4 group designed an IPMP (Intellectual Property Management & Protection) layer presenting a watermarking structure to permit monitoring, copy control and fingerprinting Mpeg-4 contents [START_REF] Lacy | Mpeg-4 intellectual property management & protection (ipmp) overview & applications document[END_REF]. This paper is devoted to present a new video-object watermarking scheme that can be employed to protect standard allowing interaction with visual content and object manipulation.

Video Object Watermarking Context

Object watermarking is quite different from bit-stream or compressed watermarking of image or video. In the field of object watermarking, the embedded mark has to be detected after object manipulations such as:

¡

This research was supported by the European IST Aspis project ¢ The insertion of a marked Video Object (VO) in a set of other VO (named VOL in the Mpeg-4 context to denote Video Object Layer).

¢ A shifting operation applied to the marked VO inside the VOL.

¢ A rotation or a scaling of the VO.

Different approaches have been designed to enable Mpeg-4 watermarking. Barni et al presented a method to mark Video Object Plans (VOP) [START_REF] Barni | Object watermarking for mpeg-4 video streams copyright protection[END_REF]. The embedding of the mark is performed modifying selected pair of DCT quantized coefficients in each VOP. The selection of the marked macroblocks is performed using a pseudo-random sequence and consequently the detection of the mark is dependant of the Mpeg-4 format. Piva et al developed an additive embedding scheme in the wavelet domain for Mpeg-4 video streams [START_REF] Piva | A dwt-based object watermarking system for the mpeg-4 video streams[END_REF]. The detection of the mark requires the decompression of the video and is invariant to format conversion. The scheme is robust to object translation and VOL modification. It is important to point out that these different schemes are not robust to object manipulations such as scaling operations or rotations because in these cases the synchronization of the mark cannot be achieved. The proposed scheme has been developed to enable signature detection after object manipulations. We focus our works on providing an automatic watermarking scheme able to orientate and scale the signature according to the object shape. Contrary to still image watermarking schemes robust to geometric transformations by embedding an artificial information to retrieve the transform [START_REF] Pereira | Fast robust template matching for affine resistant image watermarking[END_REF][7], our approach is to bound the signature with the object content. Such a scheme belongs to second generation watermarking schemes [START_REF] Kutter | Towards second generation watermarking schemes[END_REF] [START_REF] Bas | Image watermarking: An evolution to content based approaches[END_REF] where the video content is used to enable the synchronization of the mark.

Signature orientation

To detect the signature and decode the embedded message after VO rotations, we have decided to orientate the signa-ture according the principal direction of the object shape. We decided to employ Principal Component Analysis to reach such objective and obtain the principal directions angle 0 40 80 120 160 error 0 0.005 0.007 0.020 0.007 Table 1. Orientation evaluations in degree of VO "Bream" using PCA.

Signature scaling

To enable the detection of the mark after a VOP scaling operation, we extract a specific value of the VOP scale from the PCA analysis.

Supposing that the VOP, denoted ' , has been scaled by a factor S , the value T © (' % represents a real proportional to the VOP scale. Given: Table 2 illustrates the capacity of the proposed method to estimate the specific scale of the VOP. Our tests were applied on the "Akiyo" VO for scale factors varying from 1 to 0.2. In all configurations, the estimation error is under G IH P R and consequently this scale estimator is reliable.

EMBEDDING SCHEME

Our embedding scheme can be considered as an additive scheme with the particularity that the signature is inserted in an appropriate referential depending on the object shape. This scheme can be decomposed in six different step illustrated on Figure 1: 1. As presented in the previous section, a principal component analysis is performed on the VO binary mask ' . Values of ) 60 72 73 and T are extracted.

S (%)
2. A random sequence (denoted f ), composed of a set of g W G ih G p spread on " q# r" blocs, is generated from a secret key s . 3. f is thereafter scaled and rotated using ) 0 12 43 and T to obtain a sequence f ut . Each coordinate © t t are given by:

v t t xw 8 yT v i ) h ) ) ) w v h h w W T v w 8 yT X Q © ) v rh 9 h w W v w ` (1)
where © @ are the coordinate of the centre of grav- ity of the VOP shape.

We after proceed to an interpolation process using a spine-cubic convolution kernel to preserve the high frequencies of f . 4. f ut is thereafter weighted by a visual mask depending of VOP luminance to obtain the sequence f ut . We ex- ploit the fact that the human eye is less sensitive to contrast in dark or bright areas than to middle luminance areas.

5. f ut is finaly added to the object texture to create the marked object.

DETECTION SCHEME

As in classical additive schemes, the detection of the mark is performed using a correlation criterion. The detection process can be divided in five steps illustrated on figure 2.

1. As in the embedding scheme, one sequence f is gen- erated using a secret key s . scale is equal to 1. This operation is equivalent to invert equation 1:

v w 8 yT uP V © h ) v t h t t h t w W v t t w d (2) 3.
A Wiener prediction is applied on ' to minimize the texture contribution of the original object before the correlation computation [START_REF] Hernandez | Statistical analysis of watermarking schemes for copyright protection of images[END_REF].

4. The correlation value f C hg hg between i j and the random sequence j is evaluated::

f C hg hg 8 k l § m n o bp q i j © 5 (r ` j © 5 br `

5. The f C hg hg value is stoked in an accumulation variable f C hg sg 3 initialised to 0. f C hg hg 3 is thereafter compared with a threshold depending on a false-alarm probability U 7© ut v hw E . In the case of f C hg hg 3 yx U 1© zt cv hw { , the signature is consequently detected inside the VOP.

RESULTS

We have tested the presented method on the Bream sequence, composed of 300 frames in a CIF format ( | ~} " e# " ) using of the presented method is his robustness to scaling of rotation operations for different bit-rates. Finally the mask sub-sampling operation by a factor equal to seems to not affect the detection process in an important way. In our futur works we will concentrate the tests on real new segmentation conditions.

CONCLUDING REMARKS

The main idea of the presented paper is the use of Principal Component Analysis tools to perform signature detection after Video Object manipulations. VO boundary analysis permits to obtain orientation and scale information of the VO. We have used this information to create a additive scheme having low computational complexity that permits the detection of the mark after geometrical manipulations or shape modifications. Our future works will be devoted to develop embedding in the compressed domain and test real segmentation conditions.

5 :

 5 maximal variance of the data). In this context, the set of data is represented by a set of 2-D random variables ¦ ¨ § © § § that belong to the object mask ! . £ ¤ and £ ¥ represent consequently the eigenvectors of the " $# %" covariance matrix & © (' % . The main direction of the VOP, denoted ) 10 12 43 , represents the angle between the eigenvector £ ¤ and the horizontal direction of the object plan, denoted £ ) 60 72 43 98 © £ 5 A@ £ ¤ B¦ ¨C ED © F 7 Such a process permits to obtain a sharp orientation of the video object. Tabular 1 illustrates angle variation in degrees for different objects rotations of 40 degree multiples on the "Bream" VO. Results indicate the fact that the presented estimator is extremely accurate (mean precision is over G IH QP R degree).

2 .Fig. 1 .

 21 Fig. 1. Signature embedding scheme.

a 4 : 2 :Fig. 2 .Fig. 3 .

 4223 Fig. 2. Signature detection and decoding scheme.

Fig. 4 .

 4 Fig. 4. Signature detection results for different bit-rate.

Table 2 .

 2 Scaling evaluation of "Akiyo" VO using PCA.

	1 T © S ' % 2.616 2.089 1.569 1.041 0.522 0.8 0.6 0.4 0.2
	error	0	0.003 0.000 0.005 0.001