Best viewed with Microsoft Internet Explorer 5.

<Final Report for EE368 Project, Spring, 2000>

Efficient attack filter for Digital watermarking

Kyoungsik Yu

Abstract

The counter-attack method (power spectrum condition) for digital watermarking attack is described and restated using information theoretical background. Even though this derivation has same meaning with the former result [1], it offers a mathematical relationship between eigen-images of the watermark and the original image.

The performances of finite-length Wiener filter and newly proposed decision feedback attack filter were also shown. Simulation shows that the performance of finite-length filter approaches to the optimal efficiency limit of infinite-length filter, only when we neglect the quantization effects of image. The quantization of image gives a different effect to the efficiency depending on the power spectral density.

I. Introduction

With the widespread distribution of digital media contents, the protection of the intellectual property rights has become increasingly important. One of the types of media is digital image and video stream, which can be copied and widely distributed without any significant loss of quality. In this point of view, the digital watermark is a promising technique to protect the data from illicit copying [1-3]. The ideal properties of a digital watermark include the imperceptibility and robustness. The watermarked image should retain the quality of the original image as closely as possible, and the watermark should be robust to various types of image processing techniques or attacks to remove the watermark.

This report presents efficient attack methods for digital image watermarking in order to suggest desired properties that the robust watermark should have. Even though the non-causal Wiener filter is known as an optimal linear attack filter for Gaussian processes in mean-squared error sense [1], it is also true that there exist some practical problems to realize Wiener filter in an efficient manner. If we use the linear Wiener filer without any modification, the computational burden to generate the estimated watermark will be very high in general, which is not ideal for real-time processing and DSP (digital signal processor) level implementation. Moreover, Wiener filter can be unstable depending on the power spectral density of image and watermark itself. To alleviate these problems, this report suggests the finite-length Wiener filter and another efficient filtering-attack technique, so-called decision feedback filter.

In the following section II, we introduce the assumed model for analyzing digital watermarking system and derive the optimum counter-attack method in information-theoretical point of view. As a result, we will see that this is same with the power-spectrum condition derived in [1]. Section III investigates the theoretical background and formula for finite-length Wiener filter and decision feedback attack in a unified manner. In section IV, we will show the simulation results and discuss the effect of the quantization.

II. System model and the derivation of optimum counter-attack

The original image is modeled as discrete-time Gaussian random process x[n] with zero-mean, variance , autocorrelation matrix R_xx=E[x[n]x^H[n]] and power spectral density . ((×)^H means transpose-conjugate Hermitian operator. And, x[n] is assumed to be a column vector.) Similarly, the watermark w[n] is discrete-time Gaussian with zero-mean, variance , autocorrelation matrix R_ww=E[w[n]w^H[n]] and power spectral density . Two discrete-time random processes are assumed to be independent each other and wide-sense stationary. (It can be easily extended to multi-dimensional case, even though it is now assuming a one-dimensional case.) In addition, it is worth to mention that the watermark-embedded image should have integer values or finite number of quantized-levels, since the pixel values of usual image data are integers ranged from 0 to 255. We can model this quantizing effect as an additive white Gaussian noise. (This is not described in Figure 1. See Appendix for reference.)

From the direct embedding model shown in Figure 1, the watermark-embedded data can be expressed as y[n]=x[n]+w[n]. Due to the independence between x[n] and w[n], the autocorrelation and power spectral density of y[n] become R_yy=R_xx+R_ww, , respectively.

Figure 1. The schematic diagram of watermark embedding

To resist possible attacks attempting to remove the watermark, the owner wants to make the estimation of watermark w[n] from y[n] as difficult as possible. To achieve this goal, the owner can generate the sequence w[n] that minimizes the mutual information between the embedded data y[n] and the watermark w[n], I(w[n], y[n]). From [4], the definition of the mutual information between w[n] and y[n] is;

,where h(x) and p(x) mean the differential entropy and probability density function of random variable x, respectively. Using the fact that w and y are both Gaussians;

.

From previous expression, we can notice that minimizing I(w[n], y[n]) is equivalent to maximizing the matrix determinant . Now we will use following theorem of linear algebra to solve this maximization problem.

Theorem: Assume that we have eigen-value decompositions , , where U, V are unitary eigen-vector matrices and are diagonal eigen-value matrices. It is known that the determinant is maximized, if U=V.

  Using this theorem, the above expression will be maximized if both R_yy and (-R_ww) have the same eigen-vector matrix. The minus sign is trivial, as we will see soon. Note that the decompositions of autocorrelation matrices , are well-known Karhunen-Loeve transform (KLT). This means the watermark and the watermarked image should have same eigen-image.

Setting U=V, the autocorrelation matrix of the original image R_xx can be written as;

, where () is the KLT of the original image x[n]. The mutual information between the watermark and the watermarked image now becomes;

To get the fourth equality, the matrix identity |I+AB|=|I+BA| was used. are diagonal components of eigen-value matrices , respectively. Considering the energy constraints of the watermark and the original image (, ), we can use Lagrange multipliers to find the optimal condition.

Therefore, the relationship of autocorrelation matrices should be Therefore, the relation between two autocorrelation matrices become . After Fourier transform, this expression becomes , which is the same result derived in previous literature [1,2].

This confirms again the famous result; the watermark should look like the original.

III. Finite-length Wiener filter and decision feedback attack filter

If the attacker chooses the filtering as his attack method, the best attack filter to additive Gaussian watermark is a well-known Wiener filter. The frequency domain representation of Wiener filter to get the minimum mean squared error (MSE) is assuming the system model described in previous section II. However, this does not give much information about space (or time) domain representation of filter h[n], inverse Fourier transform of . Especially, the length (number of filter taps) is very important parameter for the real-world implementation of attack filter. In this section, we will derive the algorithm to find the filter coefficients of finite-length Wiener filter and decision feedback attack filter in a unified manner as described in [5,6]. In comparison with IIR (infinite-length impulse response) filter, FIR (finite-length impulse response) implementation has several advantages [7].

Figure 2. Schematic diagram of generalized filtering attack

Figure 2 shows the general attack scheme using decision feedback attack filter. It is obvious that this decision feedback attack filter degenerates to the linear Wiener filter of figure 1 if b[n]=[n]. Therefore, the decision feedback filter can be thought of as a generalization of Wiener filter, because it allows the use of the results of past decisions to estimate the value of the watermark. Generally, the decision feedback structure is a non-linear filter because of the non-linearity of decision-making function in the decoder.

The goal of attacker is to find the filter coefficient vector h[n] and b[n] to minimize the following MSE.

Here, we assume that anti-causal feed forward filter (h[n]) has N_f filter taps and finite delay of , and causal feedback filter ([n]-b[n]) has N_b filter taps (N_f > N_b+). The feedback filter should be strictly causal since we do not know the future outputs at the time of current decision. It should be noted that the feed forward filter is general finite-length non-causal filter, if we consider the effects of both finite-length delay and anti-causality of h[n]. Table 1 summarizes the notations that will be used in this section. Since the finite-length filter will not see the outside of its N_f filter taps, the important parts of the autocorrelation matrices are their first N_f x N_f elements. From now on, we will assume that the autocorrelation matrices are N_f x N_f matrices without loss of generality.

Table 1

Name	Size	Explanation	Condition
Nf	1x1	Number of feed forward filter taps
Nb	1x1	Number of feedback filter taps
	1x1	Finite delay	Nf >Nb+
h^*	1 x Nf	Transposed feed forward filter coefficients	[h[-Nf+1] h[0]]
b^*	1 x Nf	Augmented feedback filter coefficients	[1 b[1] b[Nb] 0]
Rxx	Nf x Nf	Autocorrelation matrix of the original	Rxx =Ryy -Rww
Rww	Nf x Nf	Autocorrelation matrix of the watermark	Given
Ryy	Nf x Nf	Autocorrelation matrix of embedded image	Estimated from y[n] using Welch’s method
e[n]	-	Error sequence (Assuming no error propagation)	b^*[w[n+ Nf-1] w[n]]^T - h^*[y[n+ Nf-1] y[n]]^T

Using the orthogonality condition of linear estimation theory, the MSE will be minimized when E[e[n]y^H[n]]=0. In other words,

b^HR_ww= h^H R_yy or h^H = b^H R_ww (R_yy)^-1.

For linear Wiener filter case (N_b=0),