Robustness and Efficiency of Non-linear Side-Informed Watermarking Gu´enol´e C.M. Silvestre1 , Neil J. Hurley1 , and Teddy Furon2 1
University College Dublin, Belfield, Dublin 4, Ireland {guenole.silvestre,neil.hurley}@ucd.ie 2 IRISA, INRIA, Rennes, France
[email protected]
Abstract. A number of new non-linear watermark detectors have been proposed recently [1, 2, 3] in which the watermark detection statistic is an nth order polynomial function of the extracted vector. Coupled with a side-informed watermark embedding scheme that selects a watermark to maximise the detection output, it has been shown that hypothesis tests using such detectors are highly efficient. This paper presents further analysis of these non-linear schemes, focusing in particular on the robustness of the schemes in the presence of noise and the use of periodic filtering functions in order to reduce interference from the host signal.
1
Introduction
Watermark embedding in multimedia contents proceeds by extracting a vector of features r from the original content and mixing that vector with a watermark signal w, to produce a watermarked vector rw . The watermarked vector is embedded back into the contents by inverting the extraction process. The object of watermark detection is to reliably detect the presence of the watermark signal in watermarked contents. Most state-of-the-art watermarking schemes are blind and symmetric. In blind schemes, decoding is achieved without recourse to the original signal. In symmetric schemes, the embedding of watermark information depends on a private key which is also available at the detector. Spread-spectrum watermarking [4, 5] is the most common form of blind, symmetric watermarking. A pseudo-random signal, z, is modulated on the original contents and detection relies on an hypothesis test based on the correlation of the received signal with z. Hence, the signal z can be considered as a private key, which must be available to both the embedder and detector. It was widely believed that, with the assumption that the original vectors are Gaussian, the optimum scheme was spread spectrum (SS) with a correlation detector. However, in [1] it was shown that this is not the case and a new class of watermarking schemes was proposed that use side-information to maximise the power of the detector. Recent work has focused on the development of asymmetric watermarking schemes (e.g. [6, 7]) in which detection does not rely on the same private keys F.A.P. Petitcolas (Ed.): IH 2002, LNCS 2578, pp. 106–119, 2003. c Springer-Verlag Berlin Heidelberg 2003
Robustness and Efficiency of Non-linear Side-Informed Watermarking
107
used to embed the mark. This work has lead to the investigation of detection schemes in which the detection statistic is a non-linear function of the extracted vector. In fact, Furon [8] showed that most asymmetric schemes proposed to date are second-order schemes, in that the detector determines the presence of the watermark by calculating a quadratic form on the extracted vector. With an aim towards increased efficiency and robustness, we have investigated even higher order detection schemes. By choosing the watermark signal to maximise the detection power, it is possible to achieve greater efficiency with our high-order schemes. These schemes out-perform spread-spectrum in the sense that, for a given watermark to signal power ratio and given embedded bit-rate, they result in detectors which have a greater probability of good detection (i.e. lower bit error rate). We examine two classes of side-informed detection schemes which we call JANIS [1] and POWER-n [3]. In particular, we focus on a robustness analysis of the high-order schemes. We present a first order theoretical analysis of the schemes in the presence of AWGN and validate this analysis with some experimental results. Furthermore, we investigate the use of filtering functions to boost the watermark to signal power ratio. The filtering functions are bounded, periodic mappings of the signal components. Filtering is applied by the detector and serves to reduce the variance of the input signal. The result is that the relative strength of the embedded watermark is increased. We show how filtering can be applied in conjunction with the side-informed watermark embedding to produce very powerful detection schemes.
2
Watermark Embedding and Detection
The first stage of watermark embedding is to extract an N -dimensional feature vector r from the original cover data, X, using an extraction function e, e(X, k) = r .
(1)
which typically extracts coefficients of some transform of the data. The secret key k is provided for security and is known to both the embedder and detector. The extraction process is invertible in the sense that there is an associated embedding process m(X, r) such that m(X, e(X, k)) = X .
(2)
Given an embedding strength, g, an N -dimensional watermark vector w is mixed with the feature vector r. Without loss of generality, we assume an additive mixing function, F (r, gw) = r + gw (3) where the watermark w is normalised to unit power. The watermarked content, Xw is then obtained via the embedding process: Xw = m(X, F (r, gw)).
(4)
108
Gu´enol´e C.M. Silvestre et al.
˜ proceeds by extracting Detection of the watermark from a received content X, ˜ the feature vector r = e(X). We consider detectors that calculate a real-valued detection function d(.) of the feature vector. The watermark is determined to be present if d(r) > thr , (5) for some threshold value thr. In Spread Spectrum (SS) watermarking, the detection function, d(r) = w.r is first order in the components of the feature vector. In this paper, we consider higher-order detection functions.
3
Detection Power and Efficiency
Given a significance level pf a, the threshold value thr is set to ensure that the probability of false alarm is greater than pf a. In the following, we consider r to be a set of N iid random variables. Let Q0 be the centred and normalised cdf of the detection function d under the null hypothesis H0 that the watermark is not present and let Q1 be the centred and normalised cdf of d under the alternative hypothesis H1 . Let µ0 , σ0 (resp. µ1 , σ1 ) be the mean and standard deviation of the detection function under H0 (resp. H1 ). Then, pf a = P (d > thr|H0 ) thr − µ0 ) = 1 − Q0 ( σ0 thr = σ0 Q−1 0 (1 − pf a) + µ0
(6) (7) (8)
The probability of good detection, or power of the test, is thr − µ1 ) σ1 σ0 (1 − pf a) − e) = 1 − Q1 ( Q−1 σ1 0
P (d > thr|H1 ) = 1 − Q1 (
(9) (10)
where the efficiency e is defined as e=
µ1 − µ0 . σ1
(11)
As Q1 is an increasing function, increasing the efficiency results in increasing the power.
4
Maximising the Power of Detection Using Side-Information and Filtering
Our goal is to build watermark embedding strategies and detection functions which maximise the power of detection. Let G = g 2 /σr2 be the watermark to
Robustness and Efficiency of Non-linear Side-Informed Watermarking
109
signal power ratio. In general, the value of the detection function is dependent on the embedding strength, G. The power function, p(G) = P (d(G) > thr|H1 )
(12)
gives the probability of correctly detecting the watermark given that the data is watermarked with embedding strength G and is in general an increasing function of G. 4.1
A Side-Informed Embedding Strategy
Given a detection function, in [1], it is shown that the watermark signal which maximises the power of the detector is w = k ∇d(r) ,
(13)
where denotes the component by component product and the vector k is chosen to normalise the power of w. Assuming that d is chosen such that the expected value E{d(h(r))} = 0, then, with the above choice of w, under hypothesis H1 that the watermark is present, the expected value of the output of the detector N ∂d 2 is g i=0 E ( ∂r to the first order. (r)) i 4.2
Filtering
Consider detection functions of the form d(r) = D(h(r))
(14)
where h is a non-linear mapping of the components of the received signal, h : ri → h(ri ) and h(r) is the vector which results in applying h(.) component-wise to r. We refer to h(.) as a filtering function. Its purpose is to reduce the variance of the input vector and hence increase the effective watermark to signal ratio. If we filter too much, then we run the risk of filtering out the watermark. However, our experiments have shown that filtering can significantly boost the power of detection. With filtering, Equation 13 becomes w = k [ h (r) ∇d(h(r)) ] .
(15)
Since, provided g is small, h(r + gw) ≈ h(r) + gh (r)w
(16)
the result of applying h(.) is that the effective watermark to signal power ratio is now approximately g 2 E{h2 }/σh2 . Various filtering functions can be used to define a tradeoff between robustness to external noise and capacity. Setting the watermarking signal to the gradient of a filtered signal ensures that only a limited amount of interference is
110
Gu´enol´e C.M. Silvestre et al.
introduced by the host signal. In fact, the use of periodic functions such as h(ri ) = sin(2πri /∆) is somewhat similar to watermarking methods based on quantisation [9, 10] and was also proposed in another context in [11]. The parameter pair (g, ∆) is then used in the same way as in the SCS method by Eggers et al. [9]. 4.3
Non-linear Detectors
From Section 4.1, we have a method for generating a watermarking signal to maximise the output of a given detection function. However, what is the best detection function? Consider the class of nth order polynomials of the input vector. A general nth order detector can be written as iN dn (r) = ai1 ,...,iN r1i1 r2i2 . . . rN , (17) N where the order n= k=1 ik . Initially, we consider the case where the highest power of any component of r is one and distinguish one particular subclass of such detectors, which we call JANIS. Next we investigate another subclass, called POWER-n, where one component of r is raised to the highest possible power.
5 5.1
Efficiency of Polynomial Detectors JANIS: nth Order Detection Using First Degree Polynomials
In the case where √ max (i1 , . . . , iN ) = 1, it has been shown [3] that the maximum efficiency is nN G to first order. One such class of first degree polynomial detectors is the JANIS class which has been presented in [1] and which use a detection function of the form d=
N/n n
rij
(18)
i=1 j=1
where the N vector components have been partitioned into N/n groups of n indices labelled i1 · · · in . A complete expression for the mean and standard deviation of the JANIS detector can be found in [1]. Here, we give a first-order approximation. Under hypothesis H1 that the watermark is present, the mean of the detector is given by, √ (19) E{D|H1 } = N σrn G , and the variance of the detector is as follows: V {D|H1 } =
N 2n σr (1 + nG(M4n−1 + 2(n − 1)M4n−2 − n)) , n
(20)
Robustness and Efficiency of Non-linear Side-Informed Watermarking
111
where Mk is the k th moment of the normalised distribution of r. Hence, to first order, the efficiency is nGN e= . (21) n−1 1 + nG(M4 + 2(n − 1)M4n−2 − n) 5.2
POWER-n: nth Order Detection Using Higher Degree Polynomials
Consider an nth order detector of the following form:
N/2
d(r) =
rin−1 rj
(22)
i=1
where j is a randomly chosen index, which is matched with each index i. Assuming that r is drawn from a distribution which is symmetric about the origin, then E{d} is zero for even values of n. Here we examine the case of an nth order detector where the power of a component is raised as much as possible. Rather than simply raising a single component to the nth power, we pair two components together for two reasons. Firstly, we achieve security (the detector requires a private key which determines the random pairing of the components). Secondly, the pairing ensures that both the detector and the derived watermark have zero mean. Using the side-informed watermarking method, when the watermark is present, as a first approximation, the mean of the detector is given by
N n √ σr G M2n−2 + (n − 1) M2n−4 2 The variance of d can be written as E{d|H1 } =
V {d|H1 } =
(23)
N 2n −2 σr M2n−2 1 + G M4n−4 M2n−2 + 2 −1
−3
2 2 M2n−2 + 2(2n − 2)M4n−6 M2n−4
−1 −1 M2n−2 (n − 1)(2n − 3)M4n−8 M4 M2n−4 −1 −(n − 1)2 M2n−4 M2n−2 − 1
−1
2 2 2(n − 1)M2n−4 M2n−2 −1
(24)
Hence, the dominant term of the efficiency of the POWER-n detector is given by: GN M2n−4 e
1 + (n − 1) (25) 2 M2n−2 For some distributions, this leads to a higher efficiency than obtained for the JANIS detectors. For example, if r is uniformly distributed, then e ≈ n GN/6.
112
Gu´enol´e C.M. Silvestre et al.
However, this approximation only holds while G and n are small. We can expect the power of the detector to deteriorate for large values of n. A similar scheme can be devised for odd values of n, for example
N/3
D(r) =
rin−2 rj rk .
(26)
i=1
6
Robustness to Additive Noise
Write the noise as γn where n is drawn from a Gaussian distribution with zero mean and unit variance and γ is the strength of the noise, so that K = [γ/σr ]2 is the noise to signal power ratio. With noise included and taking only terms to order K, the variance of the JANIS detector is increased by N σr2n K. The variance of the POWER-n detector is increased by N 2n σ K (M2n−2 + (n − 1)(2n − 3)M2n−4 ) . 2 r
(27)
Hence, in the case of the POWER-n detector, the contribution of additive noise to the variance of the detector is scaled by a factor proportional to n2 . We can expect the detector to become more sensitive to noise as n is increased.
7
Filtering Functions
The function h(r) processes the raw extracted vector to remove some of its variance. Hence, h(r) is typically a non-linear periodic function, which maps onto a closed interval around zero. We propose three different periodic functions of period ∆: hSAW (r) = r − ∆ round(
r ) ∆
r r
hCTS (r) = r − ∆ round( ) sign(sin(π )) ∆ ∆
(28) (29)
r ∆ sin(π ) (30) 2 ∆ If the period ∆ is small, then h(r) is approximately uniformly distributed with variance σh(r) 2 = ∆2 /12. Note that in order for the first order approximation of Equation 15 to apply, the embedding strength g must be small relative to h(r) and hence we require ∆ g. If this is not the case, then errors occur whenever the watermark extends beyond the ∆-interval containing the component to which it is added. This error is most severe in the case of hSAW and hence this is expected to perform less well than the other filters. Moreover, for small values of ∆, the filtered vector is hSINE (r) =
Robustness and Efficiency of Non-linear Side-Informed Watermarking
113
orthogonal to the original vector and thus the filtering process greatly reduces host interference. Since filtering tends to produce a h(r) which is approximately uniformly distributed, we expect that the POWER-n detector is appropriate for filtered signals. On the other hand, high orders of n are only appropriate when G is sufficiently small. Since filtering boosts G, it may not be necessary to go to high orders of the detector for robustness. There is clearly a trade-off between the amount of filtering carried out and the order (and type) of detector to use.
8
Simulation Results
The nth order watermarking schemes described above have been tested for vectors r drawn from uniform and normal random distributions. The experimental efficiency is calculated on a large set of trials and used in Equation 9 to generate a power function and ROC plot. It is assumed that the detector is normally distributed, which is justified by the fact that it is a sum of independent identically distributed random variables. Fig. 1 and 2 show the power functions and ROC curves of the JANIS and POWER-n detectors when N =2500, Pf a =10−4 and the extracted vector is uniformly distributed. The performance of the POWERn detector increases with n up to n = 14 and works well down to G = −34 dB in this case. Performance of the JANIS detector improves up to n = 6, but is much less powerful than the POWER-n detector. As expected, for both schemes, a deterioration is observed for large values of n. When the distribution is normal (Fig. 3) JANIS out-performs POWER-n. However, in practise, when r is passed through the periodic filtering function, the output distribution tends to the uniform case. The BER is plotted against different levels of WNR in Fig. 4. Although the noise term in the efficiency is scaled by factors proportional to n for both JANIS and the POWER-n detectors, they are still quite robust to noise, with the POWER-n detector performing well to WNR=-10dB. The effect of filtering is clearly shown in Figure 5. With filtering applied, the detector performs well down to G = −40 dB at order n = 2. This is due to the fact that the effective watermark to signal ratio is boosted by filtering. The relative performance of the different filtering functions is demonstrated in Fig. 6. As expected, hSAW fails at the simulated value of ∆.
9
Conclusions
Two classes of watermarking schemes have been presented which employ an nth order detection process. The optimal value of n depends on the distribution of the received signal and the watermark embedding strength. Furthermore, we have introduced a filtering process which increases the effective watermark to signal ratio by a factor proportional to the inverse square of the filtering period ∆. Similarly to spread-spectrum schemes, the robustness of these schemes to noise is dependent on the length of the extracted vector and good robustness is
114
Gu´enol´e C.M. Silvestre et al. 1
0.8 n=2 Exp n=2 Th n=4 Exp n=4 Th n=6 Exp n=6 Th n=8 Exp
Pp
0.6
0.4
0.2
0 -40
-38
-36
-34
-32
-30 -28 G in dB
-26
-24
-22
-20
(a) 1
0.8 n=2 Exp n=2 Th n=4 Exp n=4 Th n=6 Exp n=6 Th n=10 Exp n=14 Exp
Pp
0.6
0.4
0.2
0 -40
-38
-36
-34
-32
-30 -28 G in dB
-26
-24
-22
-20
(b)
Fig. 1. Experimental (dotted lines) and theoretical (plain lines) power functions for (a) a JANIS detector and (b) a POWER-n detector with Pf a =10−4 and uniformly distributed signal
achieved down to a WNR of -10 dB at a vector length of 2500. Future work will investigate an optimal setting of the values of ∆, n and G for a given distribution.
Acknowledgements This project is supported by Enterprise Ireland Strategic Research Grant ST/2000/107/Y.
Robustness and Efficiency of Non-linear Side-Informed Watermarking
115
0
10
Pp
n=2 Exp n=2 Th n=4 Exp n=4 Th n=6 Exp n=6 Th n=10 Exp n=14 Exp
-1
10 -8 10
-7
10
-6
10
-5
10
-4
10 Pfa
-3
10
-2
10
-1
10
0
10
(a) 0
10
Pp
n=2 Exp n=2 Th n=4 Exp n=4 Th n=6 Exp n=6 Th n=8 Exp
-1
10 -8 10
-7
10
-6
10
-5
10
-4
10 Pfa
-3
10
-2
10
-1
10
0
10
(b)
Fig. 2. Experimental (dotted lines) and theoretical (plain lines) ROC curves of (a) a JANIS detector and (b) a POWER-n detector for G=-26 dB and uniformly distributed signal
116
Gu´enol´e C.M. Silvestre et al.
1
0.8 n=2 Exp n=2 Th n=4 Exp n=6 Exp n=8 Exp
Pp
0.6
0.4
0.2
0 -40
-38
-36
-34
-32
-30 -28 G in dB
-26
-24
-22
-20
(a) 1
0.8 n=2 Exp n=2 Th n=4 Exp n=6 Exp n=8 Exp
Pp
0.6
0.4
0.2
0 -40
-38
-36
-34
-32
-30 -28 G in dB
-26
-24
-22
-20
(b)
Fig. 3. Experimental (dotted lines) and theoretical (plain lines) power functions for (a) a JANIS detector and (b) a POWER-n detector with Pf a =10−4 and normally distributed signal
Robustness and Efficiency of Non-linear Side-Informed Watermarking
117
0
10
-1
10
-2
10
n=4 POWERn n=6 POWERn n=2 JANIS n=4 JANIS
-3
10
-4
10 -20
-15
-10
-5
0
5
Fig. 4. BER against WNR for G=-26 dB, N=2500 and Pf a =10−4
1
0.8
D=0.22 D=0.33 D=0.50 D=0.75 D=1.15 D=1.74 D=2.63 no filtering
Pp
0.6
0.4
0.2
0 -50
-47
-44
-41
-38
-35 -32 G in dB
-29
-26
-23
-20
Fig. 5. Power functions for different values of ∆ using hCTS and the POWER-n detector with n = 2 and Pf a = 10−4
118
Gu´enol´e C.M. Silvestre et al. 1 Sine D=1.74 Continuous D=1.74 Saw-Tooth D=1.74
0.8
Pp
0.6
0.4
0.2
0 -50
-47
-44
-41
-38
-35 -32 G in dB
-29
-26
-23
-20
Fig. 6. Power functions for fixed ∆ and different filtering functions
References [1] T.Furon, G.Silvestre, N.Hurley, “JANIS: Just Another N-Order Side-Informed Scheme” in Proceedings of ICIP 2002, Oct 2002. 106, 107, 109, 110 [2] N. J. Hurley, G. C. M. Silvestre, “Nth Order Audio Watermarking” in Proceedings of SPIE 2022, Jan 2002. 106 [3] N. J. Hurley, G. C. M. Silvestre and T. Furon, “Side-Informed Watermarking using Nth-Order Polynomial Detectors”, in Proceedings of EUSIPCO 2002, 2002. 106, 107, 110 [4] I. Cox, J. Kilian, T. Leighton, and T. Shannon, “Secure spread sprectrum watermarking for multimedia,” IEEE Transactions on Image Processing 6(12), pp. 1673–1687, 1997. 106 [5] F. Hartung and B. Girod, “Watermarking of uncompressed and compressed video,” Signal Processing 66(3), pp. 283–301, May 1998. 106 [6] J. Eggers, J. Su, and B.Girod, “A blind watermarking scheme based on structured codebooks,” in IEE Colloquium on Secure Images and Image Authentication, pp. 41–46, (Savoy Place London), April 10 2000. 106 [7] T. Furon and P. Duhamel, “An asymmetric public detection watermarking technique,” in Workshop on information hiding, (Dresden, Genmany), Oct. 2000. 106 [8] T. Furon, I. Venturini, and P. Duhamel, “Unified approach of asymmetric watermarking schemes,” in Security and Watermarking of Multimedia Contents III, Proc. SPIE 4313, 22-25 January 2001. 107 [9] J. Eggers, J. Su, and B.Girod, “Asymmetric watermarking schemes,” in Tagungsband des GI Workshops Sicherheit in Mediendaten, Springer Reihe: Informatik Aktuell, (Berlin, Germany), Sept. 2000. 110 [10] B. Chen and G. Wornell, “Dither modulation: a new approach to digital watermarking and information embedding,” in Security and Watermarking of Multimedia Contents, Proc. SPIE 3657, January 1999. 110
Robustness and Efficiency of Non-linear Side-Informed Watermarking
119
[11] M. Ramkumar and A. N. Akansu, “Self-noise suppression schemes for blind image steganography”, in SPIE Multimedia Systems and Applications (Image Security) 3845, Boston, MA, Sept. 1999. 110
