Marc Chaumont
email: marc.chaumont@lirmm.fr

A Fast Embedding Technique For Dirty Paper Trellis Watermarking

This paper deals with the improvement of the Dirty Paper Trellis Code (DPTC) watermarking algorithm. This watermarking algorithm is known to be one of the best among the high rate watermarking schemes. Nevertheless, recent researches reveal its security weakness. Previously, we proposed to reinforce its security by using a secret space before the embedding. This secret space requires to compute projections onto secrets carriers. When dealing with high rate watermarking, the CPU cost for those projections is dramatically high. After introducing the watermarking scheme, we then propose two Space Division Multiplexing (SDM) approaches which reduce the complexity. Evaluations are achieved with four different attacks and show that our proposal gives better robustness results with SDM approaches.

Introduction

Dirty Paper Trellis Codes (DPTC) [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] watermarking is one of the most efficient high rate schemes. Nevertheless, it suffers of two major drawbacks: its CPU computational complexity for the embedding part and its security weakness. In this paper we propose to carry on the work proposed in [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF] which gives a nice way to improve those two drawbacks while preserving a good robustness.

The recent work of Bas and Doërr [START_REF] Bas | Evaluation of an Optimal Watermark Tampering Attack Against Dirty Paper Trellis Schemes[END_REF] about security of DPTC [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] shows that in the Kerckhoffs's framework [START_REF] Kerckhoffs | La Cryptographie Militaire[END_REF], i.e. when the embedding and extracting algorithms are known by an attacker, the trellis codebook may be retrieved observing a large number of watermarked images. Those conclusions are drawn based on a simplified version of the DPTC algorithm (non random-ordering of DCT coefficients) but show a certain security weakness of DPTC [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]. In [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF], we proposed to use a private embedding space in order to better hide the structure of the trellis. Moreover, we provided a fast embedding strategy.

The private space is obtained by vector projections. If achived directly, the vector projections give a quadratic CPU complexity. In that paper, we propose two different Space Division Multiplexing (SDM) approaches in order to reduce the quadratic complexity to a linear one. In section 2, we briefly present the embedding space and the embedding approach already presented in [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF]. In section 3, we present two SDM approaches in order to reduce the projections complexity. Finally, in section 4 we evaluate the schemes and conclude to the good behavior of the SDM approaches.

New embedding approach

In this section, we remind the embedding space and the embedding approach proposed in [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF].

Embedding space

The embedding space is obtained by first, a wavelet transform of the image, and second, a projection of the host signal x of dimension N wlt (x is the concatenation of sub-bands coefficients except LL sub-band's coefficients) onto N sec carriers of same dimension. Carriers are denoted u i with i ∈ [0, N sec -1]. Note that a projection is just a scalar product. Figure 1 illustrates the construction of the host signal x and the host vector (secret space) v x . The obtained vector v x may then be used for the informed-coding and informed-embedding (see Section 2.2).

The carriers u i are built from normalized bipolar pseudo-random sequences. For computational complexity reasons, carriers are neither orthonormalized nor drawn from a Gaussian distribution. This is not a weakness since in high dimension, carriers are orthogonal and Gaussian property is not essential. Nevertheless, computational complexity is still high since computing the N sec coefficients of the secure space requires to compute N wlt × N sec multiplications (resp. sums).

Knowing that

N wlt = N × (1 -1/2 2l ) and N sec = N × payload × N arc , it gives 1 N 2 × payload × N arc × (1 -1/2 2l
) multiplications (resp. sums). The Let us remark that it is impossible to reduce the number of multiplications and additions (thus it is impossible to reduce the complexity), and thus it is not useful to use a particular matrix multiplication routine.

Informed-coding and informed-embedding

After the projection of the host vector x onto carriers' u i , i ∈ [0, N sec -1], we obtain the host vector v x . We then run the informed-coding which is the same as the original one [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]. The informed-coding takes as input the host vector v x and the message m to be embedded and returns a codeword c * . This vector c * (of size N sec ) is the closest one to v x among vectors coming from the codebook C, and representing the message m. For more details see [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] or [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF].

The objective of the informed-embedding is to push the host vector v x into the Voronoï region of c * in order to obtain the watermarked vector v y . Many solutions exist which are either too CPU consuming [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF], either too sub-optimal considering robustness-distortion tradeoff [START_REF] Wang | Toward a Better Understanding of Dirty Paper Trellis Codes[END_REF] 2 , [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF]. In [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF], a Monte-Carlo approach is used which requires many iterations of Viterbi decoder. On a Pentium 3 GHz, for a 256 × 256 image and a message size of 1024 bits, watermarking takes from half an hour to two hours depending on the robustness threshold. In [START_REF] Wang | Toward a Better Understanding of Dirty Paper Trellis Codes[END_REF] and [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF], the Viterbi decoder is only used once or twice. On a Pentium 3 GHz, for a Our previous approach [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF] is a good compromise between complexity and robustness. It is illustrated in Figure 2 in the plane defined by v x and c * (those two vectors are noted v 2D

x and c * 2D ). This plane is usually named the Miller, Cox and Bloom plane (abbr. MCB plane).

Our approach consists in dichotomously reducing the angle between the host vector v x and the codeword c * until obtaining the smallest angle (noted θ f ) regarding all the other angles. Then, one penetrates inside the Voronoï region with a given angle θ R . Our informed embedding is thus a rotation of v x with an oriented angle equals to max(θ f + θ R , ( v x , c * )). This rotation gives the marked vector v y .

We then compute the watermark vector v w = v y -v x , retro-project it onto carriers in order to obtain the watermark signal w and then compute the watermarked signal y = x + w. The inverse wavelet transform of y gives the watermarked image. At the extraction we project wavelet coefficients onto secret carriers and then retrieve the closest codeword (and thus the message) from the codebook C.

Space Division Multiplexing (SDM) approaches

As explained in Section 2, the projections of the host signal x onto secret carriers are quadratic in (computational) complexity. In order to reduce this complexity to a more reasonable linear function, we decide to divide the wavelet space into disjoint regions and to use a carrier for each region. Figure 3 illustrates this concept. There is still N sec carriers but their non-zero values are limited to a small region. Let s = N wlt /N sec be the mean region size. The number of multiplications (resp. sums) in order to compute the secret space is now approximately

N sec × s = N wlt = N × (1 -1/2 2l
). The computational complexity is thus linear in function of the image size N . This division approach is called Space Division Multiplexing (SDM) [START_REF] Cox | 5. in Multimedia Information and Systems[END_REF].

We thus propose two approaches for SDM. In the first one, we build regions of equal size for each wavelet level (but not necessarily of equal size between the levels) and then re-arrange v x coefficients in order to obtain a fair distribution. We call this approach the structured SDM (see Section 3.1). In the second approach, we build regions of quasi-equal sizes. We name this approach the random SDM (see Section 3.2).

Structured SDM

In order to obtain region sizes belonging to N * , we solve the equation below (in the case of a 3-level wavelet decomposition):

3. N 4 1 s 789 + 3. N 16
1 s 456 + 3. N 64
1 s 123 = N sec (1)
where s 789 ∈ N * is the size of regions in the wavelet sub-bands 7, 8 or 9 and so on (see Figure 1 for sub-bands numbering). Note that the regions sizes depend on the wavelet level. Knowing that The retained solution among all the possible solutions is the one for which regions sizes are closest to3 s = N wlt /N sec . If no integer solution is found, we use overlapping on regions borders. Before projecting the host signal x onto carriers, we pseudo-randomly shuffle its coefficients by group of wavelet level (see Figure 4). This ensures a good spreading of the influences coming from coefficients of the secret space. Moreover, it improves the security, the robustness (since it breaks spatial dependencies) and the psycho-visual impact.

N sec = N × payload × N arc ,
After the projection of the host signal x onto carriers u i (carriers are built with this Space Division Multiplexing approach), we obtain the host vector v x . In order to better balance the influence distribution of the v x vector coefficients, we re-arrange it. Indeed, the first coefficients of v x are related to the low frequency wavelet sub-bands 1, 2 and 3, the next coefficients are related to higher frequency sub-bands 4, 5, and 6 etc. Thus the vector v x is re-arranged such that in each consecutive group of N arc coefficients, the probability distribution of influence is the same (see in Figure 4, the distribution influence re-arrangement).

Note that each block of N arc should respect this distribution but coefficients are again pseudo-randomly arranged in order to keep a good security level.

Random SDM

With the random SDM approach, we compute regions with no overlap, that fully cover the host vector x and whose sizes are integer and close to s = N wlt /N sec . We talk of quasi-equal regions sizes (see Figure 5).

There are N sec regions. A region r i , with i ∈ [0, N sec -1], is thus a set of contiguous wavelet coefficients, such that:

r i = {x[i]|i ∈ [ i.s , (i + 1).s -1]}, (4)
where

x[i], with i ∈ [0, N wlt -1]
, is a wavelet coefficient of the host vector x. Note that before proceeding to the projection, the host signal x is pseudorandomly shuffled in order to: break spatial dependencies, keep a good security level, and improve the robustness and the psycho-visual impact. The shuffled host signal x is then projected onto N sec carriers using SDM with quasi-equal regions' sizes (see Equation 4for regions definition). The host vector v x is the result of this projection.

Results

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

The trellis structure has 128 states with 128 arcs per states. Outputs arcs labels are drawn from a Gaussian distribution and there are N arc = 12 coefficients by output arc. The used payload is payload = 1 bit for 64 coefficients which is the same as the original DPTC algorithm [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]. The number of embedded bits is thus 1024 bits. Wavelet transform is a 9/7 Daubechies with l = 3 decompositions levels. Except the LL sub-band, all the other sub-bands are used to form the host signal x. With 256 × 256 images, the wavelet space size is thus N wlt = 64 512 coefficients. Knowing that the payload is payload = 1/64 bits per pixel and that the number of outputs coefficients for an arc is N arc = 12 coefficients, private space size is thus N sec = 1024 × 12 = 12 288 coefficients.

Four kinds of robustness attacks have been applied: Gaussian noise attack, filtering attack, valumetric attack and jpeg attack. The Bit Error Rate (BER) is the number of erroneous extracted bits divided by the total number of embedded bits. The BER is computed for each attack. Three algorithms compete with a mean distortion close to 42.4 dB:

-the algorithm detailed in [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF], having carriers of high dimension and whose projection complexity is quadratic. For this method the mean embedding PSNR is 42.42 dB and the inside angle penetration is θ R = 0.1 radian; -the structured SDM algorithm (see Section 3.1). For this method the mean embedding PSNR is 42.23 dB and the inside angle penetration is θ R = 0.05 radian. -and the random SDM algorithm (see Section 3.2). For this method, the mean embedding PSNR is 42.15 dB and the inside angle penetration is θ R = 0.11 radian.

In Figures 6,7, 8, 9, we observe that the two SDM approaches perform equal or even better results than the high dimension carriers algorithm [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF]. Results are similar for the Gaussian and the jpeg attacks, but for the filtering and the scaling attacks, the SDM approaches are better. This is a very interesting result since the high dimension carriers approach [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF] is more complex (quadratic complexity) than the two SDM approaches. The high dimension carriers approach [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF] may then be replaced with a faster (linear complexity) SDM approach.

If we compare the structured SDM approach with the random SDM approach, for the filtering and the scaling attacks, we observe that under 10% BER, the random SDM (i.e. the less complex approach) performs the best results. We conclude that in order to achieve the projection onto carriers, one should use random SDM since it is linear in complexity and it gives better robustness results than the structured SDM approach and the high dimension carriers' approach [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF].

On a Pentium 3 GHz, for a 256 × 256 image and a message size of 1024 bits, watermarking takes less than one minute for the two SDM approaches and from half an hour to two hours for the original Miller et al. algorithm [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]. In [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF], we show that our general scheme (using a secret space and a rotationbased embedding) has good robustness performances (except facing jpeg attack) compared to the original algorithm [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF] or the Lin et al. approach [START_REF] Lin | An Efficient Algorithm for Informed Embedding of Dirty Paper Trellis Codes for Watermarking[END_REF]. We conclude that our scheme [START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF], enriched with the SDM technique, provides a good distortion -payload -robustness and complexity compromise.

Moreover, we believe that it is as least as difficult for an attacker to retrieve the codebook for our random SDM approach as for the Miller et al. one [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF]. Indeed, the original approach only shuffles a subset of the DCT host coefficients whereas our approach shuffles and projects onto random carriers almost all the wavelet host coefficients.

Conclusion

In this paper, we introduce a new Dirty Paper Trellis Code (DPTC) algorithm having a security space built by projecting the wavelet coefficients onto secret carriers. In comparison to the original DPTC algorithm [START_REF] Miller | Applying Informed Coding and Informed Embedding to Design a Robust, High Capacity Watermark[END_REF], our scheme is as least as secure and the visual degradation is better adapted to the human psychovisual system. After introducing the general problem of projections, we have proposed two Space Division Multiplexing (SDM) algorithms in order to decrease the projections complexity to a more reasonable linear computational complexity. We evaluated robustness with and without SDM approaches and observed that projection with SDM approaches give more robust results than projecting with high dimension carriers. We finally observe that the random SDM approach, which is the less complex approach, is the more robust.

Fig. 1 .

 1 Fig. 1. Construction scheme of the secret embedding space.

Fig. 2 .

 2 Fig. 2. Rotation-based embedding in the Miller, Cox and Bloom plane.

  computational complexity is thus quadratic in function of the image size N . As an illustration, with a 256 × 256 image, l = 3 levels, payload = 1/64 bbp, and N arc = 12 coefficients, there are 792 723 456 multiplications (resp. sums).

Fig. 3 .

 3 Fig. 3. General Space Division Multiplexing principle.

Fig. 4 .

 4 Fig. 4. Structured SDM: Space Division Multiplexing and re-arrangements for the projection onto carriers.

Fig. 5 .

 5 Fig. 5. Random SDM.

Fig. 6 .

 6 Fig.6. Gaussian attack : BER for attack on the high dimension carriers algorithm[START_REF] Chaumont | A Novel Embedding Technic for Dirty Paper Trellis Watermarking[END_REF], on the structured SDM algorithm and on the random SDM algorithm.

Fig. 7 .

 7 Fig. 7. Filtering attack : BER for attack on the high dimension carriers algorithm [2], on the structured SDM algorithm and on the random SDM algorithm.

Fig. 8 .

 8 Fig. 8. Valumetric attack : BER for attack on the high dimension carriers algorithm [2], on the structured SDM algorithm and on the random SDM algorithm.

Fig. 9 .

 9 Fig. 9. Jpeg attack : BER for attack on the high dimension carriers algorithm [2], on the structured SDM algorithm and on the random SDM algorithm.

  Equation 1 is independent from the image size (3-level wavelet decomposition): 16 × s 123 × s 456 + 4 × s 789 × s 123 + s 789 × s 456

	-	64 3	× payload × N

arc × s 123 × s 456 × s 789 = 0.

l is the number of wavelet decompositions, payload is the number of embedded bits by pixel, and Narc is the number of output coefficients labeling an arc of the trellis.

× 256 image and a message size of 1024 bits, watermarking takes less than one minute. Nevertheless, those two last approaches degrade the image quality and are thus not fully satisfying.2 Paper[START_REF] Wang | Toward a Better Understanding of Dirty Paper Trellis Codes[END_REF] purpose is not informed-embedding but it uses a simple embedding solution.

With 3 level wavelet decomposition, payload = 1/64 and Narc = 12, the retained solution is s7,8,9 = 6, s4,5,6 =

4, s1,2,3 = 3.

With 3 level wavelet decomposition, payload = 1/64 and Narc = 12, the retained solution is n7,8,9 = 8, n4,5,6 = 3, n1,2,3 = 1.

BOWS2 data-base is located at http://bows2.gipsa-lab.inpg.fr/.

The images sub-sampling has been achieved with xnview program and using Lanczos interpolation.

Acknowledgements

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