Watermarking JPEG Images

1 Introduction

We can achieve that by adding a digital label (watermark) to the electronic media. That label must uniquely identify the copyright owner, and should also allow distribution of the particular copy to be tracked. In order to be effective, a watermark must have the following properties:

• Perceptual invisibility: watermarks should not degrade the quality of the picture being protected;
• Robustness: it should be difficult (if not impossible) to remove watermarks without significantly reducing the quality of the image. In particular, we would want to be able to retrieve the watermark after the following manipulations:
• common signal processing operations such as adding noise, change of brightness, change of contrast, and requantization;
• common geometric distortions such as translation, scaling, rotation, and cropping;
• collusion by multiple users who possess different watermarked copies of the data.

As JPEG and MPEG become compression standards for images and video respectively, it is meaningful to devise a watermarking method solely for JPEG and MPEG compressed data. Such a method can take advantage of the specific properties of image or video compression.

There have been several digital watermarking methods proposed. All of them work on uncompressed images, which makes them not particularly suited to our goals. R.G. van Schyndel et al. [vSTO94] proposed a method that inserts the watermark in the "insignificant" bits. Bits are considered insignificant if changes in them are not noticeable. That approach does not work in our case, because JPEG compression throws away those bits and thus destroys the watermark. Koch, Rindfrey and Zhao [KRZ94] proposed breaking the picture into 8x8 blocks, performing a Discrete Cosine Transform (DCT) on each block, and then encoding a 0 or 1 by modifying the relative strengths of a triple of coefficients in some blocks. Although this method works in the frequency domain, same as ours, its goal is to mark non-compressed images and is not very robust to compression. It works for JPEG compression quality factor of 50% or more, while our method performs well for quality factor as low as 10%. Cox, Kilian, Leighton and Shamoon [CKLS95] proposed a spread spectrum method -- they perform DCT on the whole image, transforming it into the frequency domain, and then embed the watermark in the largest (visually most significant) coefficients. The watermark is robust and particularly good against collusion, but their watermarking procedure is very slow, thus unusable for on-line applications.

We propose a method for watermarking JPEG images during the compression process. We are taking advantage of the round-off errors during the quantization step of JPEG compression to store the watermark. The algorithm is very efficient and the robustness to signal processing and geometric distortions is comparable to that of the spread spectrum method.

The rest of the paper is organized as follows. In Section 2, we describe the JPEG compression algorithm and introduce associated terminology. In Section 3 we show how the round-off errors during the quantization step can be used to store information. The steps of our watermarking procedure are given in Section 3.1. In Section 3.2 we explain how to extract the watermark from an image. Experimental methodology and results are presented in Section 4. Finally, conclusions and possible extensions are in Section 5.

2 Brief Review of JPEG

1. DCT on each 8x8 block: Given an image, we first divide it into 8x8 blocks and for each block, we perform a discrete cosine transformation (DCT). The result of DCT is the set of 64 DCT coefficients. The coefficient with zero frequency is called "DC coefficient" and the remaining 63 coefficients are called "AC coefficients". DC coefficient indicates the average value of the image sample block. For greyscale pictures, it is related to the overall brightness of the image.
2. Quantization: In the quantization step, each of the 64 DCT coefficients is quantized using a 64-element Quantization Table. In our implementation, an additional parameter: quantization factor (or simply called q factor) can be specified to further control the granularity of the quantization. The default value is 8. The quantization can be represented in the following formula:




F_q(u,v) = round ( (F(u,v)/ Q(u,v)) * (8/q_factor))

Where F(u,v) is the DCT coefficients before quantization, Q(u,v) is the quantization table entry, q_factor is the quantization factor and F_q(u,v) is the quantized coefficient.

3. Zigzag scan, RLE, and Entropy Coding: The quantized coefficients are reorganized in the special zigzag order and the AC coefficients are coded by Run Length Encode method (RLE). Finally we use some traditional lossless entropy coding. Usually, the Huffman coding is exploited.

3 Watermarking and Detection Algorithms

We have to define "close to *.5" precisely before going into details of the algorithms. That involves a tradeoff between robustness and quality. Suppose [*.5-a, *.5+a] is the region considered to be close to *.5, the bigger a we select, the more values we might use to plant the watermark, the lower quality the watermarked picture might be. The user can select the appropriate a according to the specific requirements of the application. We also decide not to use DC coefficients so that the watermark is robust to the changes of the overall brightness.

For the convenience of further discussion, we first give some definitions:

1. Watermark Position File: This is the file that has all the information about where to plant watermark in the corresponding semi-compressed image data.
2. Watermark Base Image File: This file stores the watermarked semi-compressed image data with "0" embedded in each position. It serves as the basis because "1"s can be embedded by adding 1 to the value in the corresponding position.

The watermarking algorithm can be divided into two steps: preprocessing phase and watermarking phase.

1. Preprocessing Phase: Preprocessing takes the original picture and the parameter a as the inputs, transform the original image into its semi-compressed format. During the quantization step, the positions where the watermark information can hide can be identified according to the given a, and then stored into the position file. We embed 0 in these positions and output as the watermark base image.
2. Watermarking Phase: In this phase, the position file, base image file (produced by preprocessing) and a specific bit pattern are provided as the inputs, and we are going to output the semi-compressed watermarked image data with the given pattern embedded. The major steps are as follows:
1. Add error-correcting code to the given bit pattern and get the coded watermark (see [MWS77] for details on error-correcting codes)
2. Embed the coded watermark into the base file with the positions provided by the position file
3. Repeat the coded watermark until all the spaces are used up
4. Perform the remaining JPEG compression steps to the semi-compressed watermarked image

Fig.1: Watermarking Algorithm

3.2 Watermark Detection Algorithm:

The watermark detection algorithm is illustrated in Fig.2, and we explain the details below. The input to the algorithm is the watermarked JPEG (possibly modified or distorted), corresponding original image with its position file and base file (these two files are not necessary stored, they can be recomputed) and the output will be the detected watermark in the given image and the raw statistics that could be used to show how reliable the result is. There are five major steps:

1. Affine Correction: As the picture might be geometrically distorted, we first try to adjust it back using some affine transformation. This problem has been studied in machine vision and methods like optical flow can be applied to get the coefficients for the transformation. Currently, we implemented a subset of the algorithm and employ a brute force way to find the best match.
2. Get the raw repeated coded watermark from the adjusted watermarked image according to the information provided by position file and base image file.
3. Standardization: as we might get some values that are not 0 or 1, we perform a standardization step to convert them to binary bits. The conversion is simply as follows: if b <= 0 then b=0 else b=1.
4. Recover coded watermark: from the standardized repeated coded watermark, we can try to recover the coded watermark by taking the bit-wise majority. The information on which the majority decisions are based are stored in the statistics file.
5. Apply error correction decoding and reveal the watermark.

Fig. 2: Watermark Detection Algorithm

4 Experiments and Evaluations

4.1 Experiments on Quality and a:

 

	Size	a=0	a=0.01		a=0.02		a=0.05		a=0.1
		SNR	# of positions	SNR	# of positions	SNR	# of positions	SNR	# of positions	SNR
F-18	640x480	29.928	1794	29.927	1913	29.905	5494	29.822	9433	29.476
flowers	640x480	23.959	4137	23.956	4710	23.950	10292	23.895	25615	23.562
lena	120x120	24.268	136	24.262	159	24.258	363	24.205	771	23.961

Table 1: The experiments were performed on three images: F-18.pgm, flowers.pgm and lena.pgm. We use SNR (sound-noise-ratio) as an indication of the quality. The SNR's listed are for the worst case, i.e. we round all the values to the direction that causes more loss. The SNR of an ordinary watermarked picture will be no worse than that. # of positions indicates the number of positions we can embed the watermark, one bit per position. The column with a=0 shows the SNR's of non-watermarked JPEG images.

4.2 Experiments on Robustness

The first group of attacks is adding random noise (plus 1 or minus 1) to the DCT coefficients, trying to remove the watermark bits that are hidden in these coefficients. The results are organized in Table 2 below. Our detection algorithm fails for the last case, but the quality of that picture is really low.

 

Parameter	SNR	Visual	Stat	Affine	Pass/Fail
10	19.700	B	10.15%	No	Pass
20	17.483	C	16.94%	No	Pass
30	15.967	C	22.24%	No	Pass
45	14.344	D	29.15%	No	Pass
60	13.190	D	32.71%	No	Fail

Table 2: Random Noise: Parameter is the number of AC coefficients per block (63 in total) that have been changed by random noise.

 

Q Factor	SNR	Visual	Stat	Affine	Pass/Fail
9	23.259	A	1.43%	No	Pass
16	18.807	B	12.56%	No	Pass
32	19.952	C	43.84%	No	Pass

Table 3: Requantization

 

Attack	Parameter	SNR	Visual	Stat	Affine	Pass/Fail
Scale	10% smaller	16.139	A	12.46%	Yes	Pass
Scale	20% smaller	15.334	A	19.38%	Yes	Pass
Scale	50% smaller	12.318	C	43.44%	Yes	Pass
Scale	10% bigger	16.139	A	12.46%	Yes	Pass
Scale	20% bigger	15.934	A	15.30%	Yes	Pass
Rotate	-15 degrees	7.89	C	16.95%	Yes	Pass
Rotate	-30 degrees	6.453	D	24.56%	Yes	Pass
Blur	3	21.102	B	35.09%	No	Pass
Blur	7	18.282	D	48.65%	No	Fail
Blur + Sharpen	3 for blurring	20.110	A	21.11%	No	Pass
Smooth	-	18.046	A	33.23%	No	Pass
JPEG compression	10% quality	13.710	C	41.13%	No	Pass
JPEG compression	5% quality	13.297	D	47.35%	No	Fail
Gamma correction	2	8.191	B	25.01%	No	Pass
Gamma correction	3	5.359	C	29.57%	No	Pass
Gamma correction	4	3.977	D	32.67%	No	Pass
Equalize histogram	-	9.451	C	30.60%	No	Pass
Dim	multiple times	4.411	B	26.78%	No	Pass
Dull	multiple times	12.017	B	28.60%	No	Pass
Sharpen	multiple times	9.860	B	26.22%	No	Pass
Black/White	-	4.315	D	41.40%	No	Pass

Table 4. Transformations by xv: The parameters in this table have the same meanings as those in xv.

5 Conclusion and Future Work

The method described here can easily be extended to MPEG compressed movies. The idea of hiding information in round-off errors can be used with any compression method that involves quantization, including some audio compression schemes. It would make the method even more powerful if we can find better ways to deal with collusion of multiple users (currently we can only recover the common part of the watermark, like the copyright owner) and modify the JPEG decoders to reject pictures with invalid watermarks would .

6 References:

[MWS77] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes,Vols. 1 and 2, North-Holland, Amsterdam, 1977

[KRZ94] E. Koch, J. Rindfrey, and J. Zhao, "Copyright protection for multimedia data", Proc. of the Int. Conf. on Digital Media and Electronic Publishing, 1994

[vSTO94] R.G. van Schyndel, A.Z. Tirkel, and C.F. Osborne, "A digital watermark", Int. Conf. on Image Processing, Vol. 2, pp. 86-90. IEEE, 1994

[Wal91] G.K. Wallace, "The JPEG still picture compression standard", CACM, Vol. 34, No. 4, pp. 30-44, 1994