ABSTRACT

This paper demonstrates how channel coding can improve the robustness of spatial image watermarks against signal distortion caused by lossy data compression such as the JPEG scheme by taking advantage of the properties of Gray code. Two error-correction coding (ECC) schemes are used here: One scheme, referred to as the vertical ECC (VECC), is to encode information bits in a pixel by error-correction coding where the Gray code is used to improve the performance. The other scheme, referred to as the horizontal ECC (HECC), is to encode information bits in an image plane. In watermarking, HECC generates a codeword representing watermark bits, and each bit of the codeword is encoded by VECC. Simple single-error-correcting block codes are used in VECC and HECC. Several experiments of these schemes were conducted on test images. The result demonstrates that the error-correcting performance of HECC just depends on that of VECC, and accordingly, HECC enhances the capability of VECC. Consequently, HECC with appropriate codes can achieve stronger robustness to JPEG—caused distortions than non-channel-coding watermarking schemes.

1. Introduction

Digital watermarking is a technique for combining digital signals with additional data, which are commonly called watermarks, so as to make the resultant signal changes imperceptible [1]. For image signals, a watermark is embedded there, and from the watermarked image the watermark is to be recovered afterward.

When the watermarked image is transmitted through image communication systems, the image is usually compressed by, for example, the JPEG coding scheme, and then transmitted to a communication channel. Hence, when it is received, the image is usually distorted due to the lossy data compression. Because the data compression is an ordinary processing in communication systems, if the watermarking is carried out before transmission, the watermark must be robust against distortions caused by at least the data compression scheme in use.

Spatial-domain watermarks, which are a kind of watermarks to be embedded into a spatial signal domain, that is, into raw signals, have generally weak robustness to subsequent signal distortions because even a small change in a signal value causes significant changes in the whole bit sequence. However, they are nevertheless used in a number of applications such as steganography and fragile watermarking for content authentication.

Error correction techniques of channel coding such as the BCH (Bose-Chaudhuri-Hockquenghem) codes can be used to improve the robustness of spatial-domain watermarks [2]. A number of the related coding methods were studied in the late 1990’s [3]. Most of the error-correction coding (ECC) methods have been applied to transform-domain watermarks, for instance, in [4].

It has been reported in [5] that the error-correction coding in Gray codewords is more effective than that in natural binary codewords for JPEG-DCT compression. In the method, a watermark bit is encoded with an errorcorrecting block code, and the generated codeword is embedded in the bit sequence of a pixel that is expressed in Gray code. Thus, a watermark bit is embedded in each pixel with a protection from the change in pixel level. We here refer to this method as the vertical error-correction coding (VECC), meaning the coding in the vertical direction of the pile of image bit-planes.

The characteristic of bit changes in pixels caused by the JPEG-DCT coding generally differs from that of bit errors occurring in communication channels; the bit error rate under the JPEG compression with a usual image quality is generally much larger than that under a usual channel condition. This paper focuses on the protection of spatial watermarks against JPEG lossy compression. Toward this purpose, we propose a scheme of encoding watermark bits in an image plane with channel coding, to which we refer as the horizontal error-correction coding (HECC), while using the VECC method to embed the generated code bits into pixels. By the experiment of watermarking and JPEG coding, we demonstrate how effectively the HECC can actually perform to improve the robustness of spatial watermarks for the JPEG lossy compression. To simplify the evaluation of the coding performance, simple one of error-correcting block codes is used in the HECC.

The rest of this paper is organized as follows: In Section 2, the properties of the Gray code, which play an essential role in the proposed scheme, is explained. In Section 3, the schemes for watermarking spatial image signals by error-correction coding are described; first, the VECC based on [5] is described, and then, the HECC is specified. In Section 4, the performance of HECC is evaluated from the results of some experiments conducted on test images of natural scenery. The degree of robustness that the scheme achieves against JPEG-DCT compression is discussed in comparison with that a typical one of non-channel-coding watermarking schemes performs. Section 5 concludes the paper.

2. Properties of Gray Code

2.1. Difference between Adjacent Codewords

As regards the properties of Gray codes, it is well known the fact that any two adjacent codewords differ in only one bit-position. The bit-position is definitely given as follows: Let C_G denote the m-bit Gray code and C_G (v) be the codeword in C_G associated with a signal level v, where. The bit-position, h, where and differ is given by

, (1)

where the bit-position 0 indicates the least significant bit (LSB). In addition, we find out that if v is odd.

2.2. Difference between Two Codewords

As for, the difference between and is given by the result of accumulating bit changes from through. Hence, these two codewords differ in those bit positions where the bit inversion occurs once or odd times during the accumulation. Thus, one or more bits differ between the codewords, and the difference bit-positions are determined from the starting level v. Consequently, the distribution of the difference bits in m bits for all the possible v’s is derived using Equation (1).

Letting m = 8 as a practical example, Figure 1 illustrates the distributions of the difference bits in 8-bit Gray codewords, , for each value of d from 1 to 4,

for instance. As an example, for d = 1, out of 255 possible codeword pairs, 128 pairs differ in the bit-position g₀, 64 pairs in g₁, 32 pairs in g₂, 16 pairs in g₃, 8 pairs in g₄, 4 pairs in g₅, 2 pairs in g₆, and one pair in g₇. Thus, for a given difference signal-level d, with regard to pairs of two codewords whose levels are apart by d from each other, the number of bit positions where the two Gray codewords differ lies in a narrower range than the number of bit positions where the two natural binary codewords differ.

3. Error-Correction Coding Scheme

Figure 2 shows the data structure in the horizontal and vertical error-correction coding schemes. Figure 3 illustrates a diagram of the HECC scheme involving VECC scheme in the use of the data structure. In the following, first, the VECC scheme is developed, and then, the HECC scheme is explained.

3.1. Vertical Error-Correction Coding

Taking advantage of the above properties of Gray codes, error-correcting codes can correct difference bits caused in Gray codewords by level changes more effectively than those caused in natural binary codewords. In the VECC scheme, one watermark bit is to be embedded into the bit pattern of one pixel by the error-correcting in Gray codes: Suppose that signal levels are expressed in m-bit Gray codes. Three bits in a Gray codeword, denoted by a set of, is replaced with a (3, 1)

single-error-correcting (SEC) codeword, where g_l is the lth bit of the Gray codeword for, and g₀indicates the LSB. The scheme with the above l value is referred to as ECC_Gl,. An information bit of the (3, 1) SEC code corresponds to a watermark bit. Note that the (3, 1) code is the simplestone of the (n, k) code depicted in Figure 3.

In embedding a watermark bit into a pixel, the natural binary codeword representing the source level is first converted to a Gray codeword. Either one of the two SEC codewords that is associated with the watermark bit is chosen and put in the Gray codeword. The resulting Gray codeword is, then, converted back to a natural binary codeword. As a result, the difference in signal level between the source and encoded natural binary codewords leads to a spatial distortion. We refer to such a distortion caused by the embedding of watermarks as an embedding distortion.

In a (3, 1, 3) code, there exist the following four kinds of pair of 3-bit codewords that are apart from each other by the Hamming distance of 3: 1) {(000), (111)}; 2) {(001), (110)}; 3) {(011), (100)}; and 4) {(010), (101)}. On the assumptions both that each m-bit level is equally likely to occur at any signal and that a watermark bit is a random variable, the amount of embedding distortions was estimated by an expected value of mean square er-

rors (MSEs) between codewords. As a result, for ECC_G0, the codeword pair 4), denoted by C_EG, that yields the smallest distortion has been selected. C_EG also applies to ECC_G1 to minimize embedding distortions.

Now that C_EG is given, two encoded levels corresponding to respective watermark bit-values of 0 and 1 are determined for each source level. Figures 4(a) and (b) show the relationship between source levels and encoded levels in ECC_G0 and ECC_G1, respectively. The relationship repeats periodically over the 8-bit dynamic range every 16 levels in ECC_G0, every 32 levels in ECC_G1. ECC_Gl with l > 1 is no longer practical for 8-bit signals due to large embedding distortions.

Also, we define a pixel correct probability, R_P, by the proportion of correctly recovered ones of the embedded

C_EG codewords. As reported in [5], ECC_G1 possesses a larger R_P for level changes than ECC_G0. At the same time, however, the embedding distortion caused by ECC_G1 gets so large that it tends to get perceptible and similar to false contours [6] particularly in smooth image areas.

3.2. Horizontal Error-Correction Coding

To improve the robustness of the embedded watermarks to level changes, another error-correction coding is applied to pixel blocks where the ECC_G0 scheme is applied to each pixel to encode each bit of the error-correcting codeword. Suppose that codewords in a (n, k) t-errorcorrecting code are to be embedded into blocks of n pixels. Here, k information bits of the code correspond to watermark bits. Roughly speaking, if the ratio is larger than the pixel correct probability R_P, this code is expected to work effectively.

On the basis of the result of a preliminary experiment regarding the properties of R_P, the values of R_P above 1/2 are supposed. Accordingly, a (3, 1) SEC code is used for the coding scheme here, namely, n = 3 and k = 1. Also, two codewords (010) and (101) such that both have alternate bit-patterns are assigned to the code and associated with the respective values of a watermark bit 0 and 1. We refer to this horizontal error-correction coding scheme involving ECC_G0 as HECC_G0.

4. Experiment and Results

4.1. Experimental Method

1) Implementation of watermarking: Experiments of the watermarking schemes were conducted in the following way: four 8-bit monochrome images of 256 by 256 pixels, Lena, Aerial, Peppers, and Parrots, which are commonly used in image research, were used as source images. The watermark bits were generated by a pseudorandom number generator with a computer. The whole of each source image was divided to row-wise 3-pixel blocks to implement HECC_G0, excluding the residual pixels at the right end of the image.

Here, we define a watermarking rate by the ratio of the number of watermark bits to the number of pixels carrying them, denoted by τ (bits/pixel), which is similar to the code rate in channel coding. We also define an embedding ratio, denoted by ρ, by the proportion of pixels selected to use in the whole source image. Suppose that a given source image consists of N pixels, then, the number of watermark bits embedded in the image is given by. HECC_G0 was performed with τ = 1/3 (bits/pixel) and in the experiment. Note that the watermarking is actually to be implemented with so as to conceal the locations where watermarks are embedded in the image.

2) Implementation of JPEG coding: Each watermarked image was encoded by the JPEG DCT-baseline coding scheme, and then, the resulting data were decoded to reconstruct the image. To obtain various amount of coding distortion, the JPEG coding performance was varied by modifying the luminance-quantization matrix that is specified as the recommended one in [7].

From the reconstructed image, first, the vertical (3, 1)-SEC codeword at each pixel is decoded. Then, the horizontal (3, 1)-SEC codeword at each pixel-block is decoded. Here, we define a block correct ratio, R_B, by the proportion of correctly recovered ones of horizontal SEC codewords. The block correct ratio can be regarded as the watermark recovery ratio of HECC_G0, denoted by R_W, which is defined by the proportion of correctly recovered ones of embedded watermark bits.

3) Pixel surrounding method: As in [5], the pixel surrounding method (PSM) [8] was used for the performance comparison with the error-correcting watermarking schemes. The procedures and properties of PSM are outlined below.

To embed a watermark bit w into a selected pixel x in a cover image f, the mean value, a, of the eight pixels surrounding x in the 3 × 3 neighborhood is calculated, and then, letting denote a signal level of the pixel x, is replaced with the value if, or otherwise, where δ is a specified level. Consequently, the source image is not only low-pass filtered but also subjected to signal variation of δ as a result. The locations of selected pixels are to be kept secret.

To extract watermark bits from a given image, at the pixel x' of corresponding to the selected x of f, the mean value, , of the eight pixels surrounding x' is calculated, and then the watermark bit w' is determined as 0 if, or 1 otherwise. Thus, the watermarking rate τ of PSM is 1 (bit/pixel) in this experiment.

Suppose that the embedding at each selected pixel is carried out independently in the source image. If two of the selected pixels are adjacent in the 3 × 3 neighborhood, the watermark bits extracted from these pixels are likely to be wrong due to unexpected differences between the mean value calculated before watermarking and that calculated after watermarking. Thus, the watermarked image is likely to be already somewhat corrupted without subsequent distortions, particularly in the case of large ρ over 1/9.

4.2. Experimental Results

1) Embedding distortions: The amount of embedding distortions was estimated by the mean square error (MSE) between the entire source and the entire watermarked image. Here, the PSM was implemented for each source image with the embedding ratio for comparison with HECC_G0 under the condition of embedding the same number of watermark bits.

Table 1 lists the MSEs of the watermarked images generated by HECC_G0 and by PSM with various embedding depth δs for the four test images, in terms of peaksignal-to-noise ratios (PSNRs) in decibel (dB). The amount of embedding distortions caused by HECC_G0 is much less than those caused by PSM, by more than 6 dB of PSNR. Although another experimental result shows that, compared with PSM with, the distortion caused by PSM with is reduced by an increase of about 5 dB in PSNR, the distortion tends to increase with the parameter δ as shown in Table 1.

Weighted signal-to-noise ratios (WSNRs) of the watermarked images are also listed in Table 1. These values were measured under the condition of both the viewing distance of 13 inches and the displaying pixel-density of 200 pixels/inch. Any watermarked image of HECC_G0 shows the WSNR over 42 dB, still about 6 dB larger than the watermarked images of PSM.

Table 1 also includes the watermark recovery ratios. As mentioned before, some of the embedded watermark

bits are likely to be already lost in the PSM-watermarked images. To increase the recovery ratio, it is necessary to increase the parameter δ.

To observe image appearance, examples of the watermarked images are shown in Figure 5. HECC_G0 hardly yields perceptible distortions over the resulting images as shown in Figure 5(b). As seen in Figure 5(c), on the contrary, PSM makes the watermarked image look blurred and corrupted. Such degradation looks prominent in Figure 5(c’) where the image consists of a lot of small objects.

2) Effects of horizontal SEC coding: Both the pixel correct probabilities R_P and the block correct ratios R_B were measured from a set of the watermarked images of the four test images that had been distorted by JPEG compression in various degrees. As shown in Figure 6, the correlation between them agrees well with the theoretical relation, that is,. This experimental result indicates that HECC_G0 is as effective as expected according to the bit rate given by VECC for actual images such as those of natural scenery.

3) Robustness for JPEG-distortions: Figure 7 shows the robustness of each watermarking scheme to distortions caused by JPEG coding for the four test images, with the watermark recovery ratios plotted against the amount of distortions measured in PSNR. For any of these test images, HECC_G0 shows a definite improvement in the robustness over the ECC_G0 while the watermark recovery ratio is still lower than that of ECC_G1. Although the robustness performance of HECC_G0 is nearly comparable to that of PSM with for PSNR below 40 dB,

it gets even superior to that of PSM with a larger δ beyond 40 dB. Note that PSM with achieves larger watermark recovery ratios than PSM with. Also, PSM can hardly achieve the complete watermark recovery even for the images of high PSNR due to the initial degradation as listed in Table 1, which is observed particularly in Figure 7(b).

5. Conclusion

The code that has been used in HECC in the experiment is a (3, 1) single-error-correcting code. For this code, the actual performance with respect to error-correction for the test images of natural scenery under the condition of being distorted by JPEG DCT-baseline scheme was measured. With respect to the performance of VECC, it has been observed from the experimental result that those pixels which result in the extraction of wrong bits are distributed almost uniformly in the whole JPEG-distorted image. This fact shows the evidence that the error-correcting code of HECC performs according to the pixel correct probabilities of VECC. Thereby, HECC enhances the capability of VECC to recover watermark bits from distorted images, and accordingly, achieves stronger robustness to JPEG-distortions particularly for high-quality images than the non-channel-coding and filter-based PSM. According to the above conclusion, we can consider the use of sophisticated codes in HECC, such as BCH codes,

REFERENCES