# Adaptive Watermarking Scheme Using Biased Shift of Quantization Index

Authors: Young-Ho Seo; Hyun-Jun Choi; Ji-Sang Yoo; Dong-Wook Kim
Journal: Journal of Electrical and Computer Engineering
 (2010)

---

## Abstract

We propose a watermark embedding and extracting method for blind watermarking. It uses the characteristics of a scalar quantizer to comply with the recommendation in JPEG, MPEG series, or JPEG2000. Our method performs embedding of a watermark bit by shifting the corresponding frequency transform coefficient (the watermark position) to a quantization index according to the value of the watermark bit, which prevents from losing the watermark information during the data compression process. The watermark can be embedded simultaneously to the quantization process without an additional process for watermarking, which means it can be performed at the same speed to the compression process. In the embedding process, a Linear Feedback Shift Register (LFSR) is used to hide the watermark informations and the watermark positions. The experimental results showed that the proposed method satisfies enough robustness and imperceptibility that are the major requirements for watermarking.


---

## Body

## 1. Introduction

As digital data, especially the image/video data that is the most information-rich, has been used as a commercial media very popularly, the ownership of the digital contents has been major issue to be solved. Digital watermarking has been known as the best solution as the ownership protection technique.A watermarking scheme mainly consists of two processes: (1) deciding target data to embed the watermark in (watermark positions) and (2) embedding watermark data. Both affect the watermarking performance, robustness and imperceptibility. In this paper, we only concern with the embedding method itself, not proposing the watermark positioning method.The target data to embed watermark in has been transferred from the ones in spatial domain to frequency domain as the watermarking techniques have been developed. A watermark embedded in a frequency domain data has been known to show better robustness against attacks than the spatial domain data. Thus, recent research has focused on the frequency domainwatermarking.Cox et al.[1] proposed watermarking schemes embedding the watermark into the frequency domain based on the Discrete Cosine Transform (DCT).Hsieh et al.[2] used the multiresolution property of the Discrete Wavelet Transform (DWT). The adoption of JPEG2000 [3] as a standard for still image compression technique has speeded up these researches [2, 4].Yasein and Agathoklisproposed a JPEG2000-based watermarking technique that embeds watermark into the lowest subband using error correction code [5]. As 3D (3-dimensional) image and graphics are widely researched recently, watermarking schemes for 3D mesh object have been also proposed [6].This paper is to propose a watermark embedding method that uses characteristics of a scalar quantization which is commonly used in a data compression technique for 2D images such as JPEG [3], MPEG series [7], and JPEG2000 [3]. That is, the proposed method can be applied to any watermark positioning method complying with such a compression technique. Thus, we do not include a specific watermark positioning scheme here. The purpose of our method is to embed the watermark during the quantization process without additional process for watermarking itself. Quantization is generally used for a lossy compression in JPEG, MPEGs, or JPEG2000 standard. Thus, the speed to perform the watermarking scheme with our method is exactly the same as to perform the data compression process. Another intention of our method is to lose as small as possible watermarked data by quantization robustness. One more purpose of it is to minimize the quality degradation due to watermarking (imperceptibility) by limiting the variance of a coefficient within a half of a quantization step size. Since the watermarking is executed without a special calculation process during quantization, it is possible to minimize the delay time to embed/extract watermark in a realtime.


## 2. Proposed Watermarking Scheme

Since an image/video is mostly used in a compressed form, one must consider the information loss during the compression process. The main reason is to quantize coefficients, which corresponds to an essential tool for lossy compression. Therefore our research deeply considers the relationship between quantization and watermarking to propose an adaptive watermark embedding scheme.The quantization in the JPEG, MPEGs, and JPEG2000, the international standards for the still image or motion picture, is a lossy compression process which is executed by dividing a coefficient by a predefined value that is called quantization step size. Equations (1) or (2) shows the quantization process for JPEG/MPEGs and JPEG2000, respectively.(1)qb(u,v)=round(ab(u,v)Δb(u,v)),(2)qb(u,v)=sign(ab(u,v))·⌊|ab(u,v)|Δb+0.5⌋,
where, ab(u,v) and qb(u,v) are the pixel values at (u,v) before and after quantization, respectively, with the quantization step size of Δb(u,v). Here, the subscript b represents a subband or a region resulting from a transformation from a space domain into a frequency domain. Also, round(x) means the function is to round up to integer, which is the same function to ⌊x+0.5⌋ in (2), in which ⌊x⌋ means the largest integer not greater than x. sign(x) is the sign of x.


### 2.1. Watermark Embedding

The proposed scheme uses a biasedshift of a quantized coefficient (or index) according to the watermark value and the coefficient to embed the watermark in. Before embedding the watermark, we scatter the watermark itself for safety. In this paper, we use an (m+n)-bit LFSR whose representative feedback characteristics are expressed by (3) when the watermark data is a 2D data with the size of 2m×2n, which is shown in Figure 1(3)P(x)=xm+n-1+am+n-2xm+n-2+⋯+a1x+a0.Figure 1
A linear feedback shift register (LFSR).In this equation, the coefficients (ai∈{0,1}) have a set of values to make the polynomial primitive. In Figure 1, each block of ai is a switch to connect the feedback to the corresponding XOR gate (⊕). In the figure, Si is the storage element that operates by a clock and its output zi is one of the outputs of this LFSR. The initial value of the LFSR (keyLFSR in Algorithm 1) can be arbitrary except all “0” and is used as a secret key in this paper to hide the watermark to an unauthorized person.Algorithm 1:Rearrangement algorithm for watermark data
Procedure{Watermark_Mix}input: 2m×2n  original 2D watermark(w(i,j))LFSR=(zm+n-1, zm+n-2, …, z1, z0)output: 2m×2n  rearranged 2D watermark(w′(i,j))begin{k=1;for   i=0  to  2m-1{for   j=0  to  2n-1w(k++)=(w(i,j));}initializeLFSRwith key(keyLFSR);w′(0,0)=w(0);for  I=1  to  2m+n-1{apply one clock toLFSR;xi=zm+n-12m-1+zm+n-22m-2+⋯+zn+121+zn20;yi=zn-12n-1+zn-22n-2+⋯+z121+z020;w′(xi,yi)=w(i);}}end{Watermark_Mix}With this LFSR, we composed a data rearrange scheme as shown in Algorithm1. It first converts the accepted 2D watermark data into a serial data. Then, it is repositioned by the parallel outputs (Zi′s) of LFSR such that they are partitioned into two parts to decide the x and y coordinates.The proposed watermark embedding scheme directly adjusts the transformed coefficients by considering the quantization scheme and each watermark bit. The data adjustment is performed by a biased shift method shown in (4) or (5), where ⌈x⌉ means the smallest integer not less than x,(4)ab′(u,v)=sign(ab(u,v))·⌊|ab(u,v)|Δb(u,v)⌋×Δb(u,v),(5)ab′(u,v)=sign(ab(u,v))·⌈|ab(u,v)|Δb(u,v)⌉×Δb(u,v).If watermarking is not considered, the quantization makes the transformed coefficientab(u,v) the value of the nearest multiple of the quantization step Δb(u,v) as (1) or (2). Our watermarking scheme shifts this quantized coefficient (QC) or index. The amount and the direction of the shift are determined by the Least Significant Bit (LSB) of the resulting QC and the corresponding watermark bit in the manner that the LSB of the QC would be the same as the watermark bit by using (4) or (5). This process includes four cases, and the processing method for each of them is described in Algorithm 2.Algorithm 2:Watermark embedding procedure.
Procedure{Watermark_Embedding}begin{initializeLFSRwith a key(keyembed);for   i=0  to  2m+n-1{if   (LFSRp(i)=``1")  then    {if  (LFB(⌊|ab(u,v)|/Δb(u,v)⌋)=``0")  then    {if  (wi=0) then embedwi  by (4);else       embedwi  by (5);}if   (LFB(⌊|ab(u,v)|/Δb(u,v)⌋)=``1")  then    {if  (wi=0) then embedwi  by (5);else       embedwi  by (4);}}apply one clock toLFSR;  }end{Watermark_Embedding}With this watermarking process, the maximum amount of shift by watermarking is one quantization step. If the occurrence probabilities of the four cases are the same, the average amount of shift is zero. In Algorithm2, LFSRp(i) means the value of output zp by applying i clocks with the LFSR initial value keyembed. Also LSB(x) means the LSB of x.In this paper, we consider one more scheme to hide the watermarking positions with an LFSR, which might be the same to or different from the one to scatter the watermark data. The method is to select some QCs from the mark space, the target domain of the QCs to be watermarked, according to the value from the LFSR. There can be two schemes as follows. Note that it is out of this paper's scope how to select the mark-space.(1)
Use a serial output of an LFSR. The output bit stream is matched to the QCs in the mark space and only the QCs whose LFSR bits are “1” are selected as the watermarking positions. This method only embeds in the half of the QCs in the mark space if “0” and “1” have the same occurrence probability in the LFSR output.(2)
Usek parallel outputs. The value with k LFSR outputs is used as the value to skip the QCs in the mark space. That is, if the value is q, the next watermark position would be the (q+1)th QC from the previously selected QC. With this method, only 2/(2k+1) QCs from the mark space would be selected as the watermark positions if each k-bit combination by the k outputs has the same occurrence probabilities.Algorithm2 includes this random selection scheme. Here, only the first method is included such that LFSRp(j).


### 2.2. Watermark Extracting

The embedded watermark is extracted only when the watermark information is required. It should be extracted from the watermarked data without support of the original data since the scheme is blind watermarking. The extraction process of our scheme needs to decide if a watermark bit resides in a specific data and the value of the watermark bit if resides.Existence of watermark bit is determined using the same LFSR(s) and their initial values as the one(s) used in embedding process. The procedure is exactly the same as in embedding, and it is not mentioned further here. The embedded watermark is extracted only when the watermark information is required. It should be extracted from the watermarked data. The extraction process of our scheme needs to decide if a watermark bit resides in a specific data and the value of the watermark bit if resides.Existence of watermark bit is determined using the same LFSR(s) and their initial values as the one(s) used in embedding process. The procedure is exactly the same as the one of embedding, and it is not mentioned further, here.The process to read out the watermark bit is depicted in Algorithm3. If the transmitted data containing a watermark bit has the value of even (odd) step of quantization, the corresponding watermark bit is “0” (“1”). In a real process, the received content data rb(u,v) is dequantized as ab′′(u,v)=rb(u,v)×Δb′(u,v), where Δb′(u,v) is the quantization step for real compression, and the result is analyzed by (6) where m and n are arbitrary integer, which decides the extracted watermark bit wi′. Note that Algorithm 3 includes the process to decide existence of a watermark bit when a serial LFSR bit is used. Also, it includes the step to reform the 2D watermark data(6)wi′={0,(2m-1)Δb(u,v)≤ab′′(u,v)<(2m+1)Δb(u,v),1,(2n+1)Δb(u,v)≤ab′′(u,v)<(2n+3)Δb(u,v).Algorithm 3:Watermark extraction procedure
Procedure{Watermark_Extraction}begin{initializeLFSRwith a key(keyembed);for   i=0  to  2m+n-1{if   (LFSRp(i)=``1")  then    {if(⌊(ab′′(u,v)+Δb(u,v)/2)/Δb(u,v)⌋=even)  thenwi′=``0"  by (6);elsewi′=``1"  by (6);  }}initializeLFSRwith key(keyLFSR);for  I=1  to  2m+n-1{xi=zm+n-12m-1+zm+n-22m-2+⋯+zn+121+zn20;yi=zn-12n-1+zn-22n-2+⋯+z121+z020;w′′(xi,yi)=w′(i);}}apply one clock toLFSR;  }end{Watermark_Extraction}The extraction process needs only a few decision tasks so that its speed degradation on the decoding time is negligible, even though the watermark is not necessarily extracted in each decoding process.


## 2.1. Watermark Embedding

The proposed scheme uses a biasedshift of a quantized coefficient (or index) according to the watermark value and the coefficient to embed the watermark in. Before embedding the watermark, we scatter the watermark itself for safety. In this paper, we use an (m+n)-bit LFSR whose representative feedback characteristics are expressed by (3) when the watermark data is a 2D data with the size of 2m×2n, which is shown in Figure 1(3)P(x)=xm+n-1+am+n-2xm+n-2+⋯+a1x+a0.Figure 1
A linear feedback shift register (LFSR).In this equation, the coefficients (ai∈{0,1}) have a set of values to make the polynomial primitive. In Figure 1, each block of ai is a switch to connect the feedback to the corresponding XOR gate (⊕). In the figure, Si is the storage element that operates by a clock and its output zi is one of the outputs of this LFSR. The initial value of the LFSR (keyLFSR in Algorithm 1) can be arbitrary except all “0” and is used as a secret key in this paper to hide the watermark to an unauthorized person.Algorithm 1:Rearrangement algorithm for watermark data
Procedure{Watermark_Mix}input: 2m×2n  original 2D watermark(w(i,j))LFSR=(zm+n-1, zm+n-2, …, z1, z0)output: 2m×2n  rearranged 2D watermark(w′(i,j))begin{k=1;for   i=0  to  2m-1{for   j=0  to  2n-1w(k++)=(w(i,j));}initializeLFSRwith key(keyLFSR);w′(0,0)=w(0);for  I=1  to  2m+n-1{apply one clock toLFSR;xi=zm+n-12m-1+zm+n-22m-2+⋯+zn+121+zn20;yi=zn-12n-1+zn-22n-2+⋯+z121+z020;w′(xi,yi)=w(i);}}end{Watermark_Mix}With this LFSR, we composed a data rearrange scheme as shown in Algorithm1. It first converts the accepted 2D watermark data into a serial data. Then, it is repositioned by the parallel outputs (Zi′s) of LFSR such that they are partitioned into two parts to decide the x and y coordinates.The proposed watermark embedding scheme directly adjusts the transformed coefficients by considering the quantization scheme and each watermark bit. The data adjustment is performed by a biased shift method shown in (4) or (5), where ⌈x⌉ means the smallest integer not less than x,(4)ab′(u,v)=sign(ab(u,v))·⌊|ab(u,v)|Δb(u,v)⌋×Δb(u,v),(5)ab′(u,v)=sign(ab(u,v))·⌈|ab(u,v)|Δb(u,v)⌉×Δb(u,v).If watermarking is not considered, the quantization makes the transformed coefficientab(u,v) the value of the nearest multiple of the quantization step Δb(u,v) as (1) or (2). Our watermarking scheme shifts this quantized coefficient (QC) or index. The amount and the direction of the shift are determined by the Least Significant Bit (LSB) of the resulting QC and the corresponding watermark bit in the manner that the LSB of the QC would be the same as the watermark bit by using (4) or (5). This process includes four cases, and the processing method for each of them is described in Algorithm 2.Algorithm 2:Watermark embedding procedure.
Procedure{Watermark_Embedding}begin{initializeLFSRwith a key(keyembed);for   i=0  to  2m+n-1{if   (LFSRp(i)=``1")  then    {if  (LFB(⌊|ab(u,v)|/Δb(u,v)⌋)=``0")  then    {if  (wi=0) then embedwi  by (4);else       embedwi  by (5);}if   (LFB(⌊|ab(u,v)|/Δb(u,v)⌋)=``1")  then    {if  (wi=0) then embedwi  by (5);else       embedwi  by (4);}}apply one clock toLFSR;  }end{Watermark_Embedding}With this watermarking process, the maximum amount of shift by watermarking is one quantization step. If the occurrence probabilities of the four cases are the same, the average amount of shift is zero. In Algorithm2, LFSRp(i) means the value of output zp by applying i clocks with the LFSR initial value keyembed. Also LSB(x) means the LSB of x.In this paper, we consider one more scheme to hide the watermarking positions with an LFSR, which might be the same to or different from the one to scatter the watermark data. The method is to select some QCs from the mark space, the target domain of the QCs to be watermarked, according to the value from the LFSR. There can be two schemes as follows. Note that it is out of this paper's scope how to select the mark-space.(1)
Use a serial output of an LFSR. The output bit stream is matched to the QCs in the mark space and only the QCs whose LFSR bits are “1” are selected as the watermarking positions. This method only embeds in the half of the QCs in the mark space if “0” and “1” have the same occurrence probability in the LFSR output.(2)
Usek parallel outputs. The value with k LFSR outputs is used as the value to skip the QCs in the mark space. That is, if the value is q, the next watermark position would be the (q+1)th QC from the previously selected QC. With this method, only 2/(2k+1) QCs from the mark space would be selected as the watermark positions if each k-bit combination by the k outputs has the same occurrence probabilities.Algorithm2 includes this random selection scheme. Here, only the first method is included such that LFSRp(j).


## 2.2. Watermark Extracting

The embedded watermark is extracted only when the watermark information is required. It should be extracted from the watermarked data without support of the original data since the scheme is blind watermarking. The extraction process of our scheme needs to decide if a watermark bit resides in a specific data and the value of the watermark bit if resides.Existence of watermark bit is determined using the same LFSR(s) and their initial values as the one(s) used in embedding process. The procedure is exactly the same as in embedding, and it is not mentioned further here. The embedded watermark is extracted only when the watermark information is required. It should be extracted from the watermarked data. The extraction process of our scheme needs to decide if a watermark bit resides in a specific data and the value of the watermark bit if resides.Existence of watermark bit is determined using the same LFSR(s) and their initial values as the one(s) used in embedding process. The procedure is exactly the same as the one of embedding, and it is not mentioned further, here.The process to read out the watermark bit is depicted in Algorithm3. If the transmitted data containing a watermark bit has the value of even (odd) step of quantization, the corresponding watermark bit is “0” (“1”). In a real process, the received content data rb(u,v) is dequantized as ab′′(u,v)=rb(u,v)×Δb′(u,v), where Δb′(u,v) is the quantization step for real compression, and the result is analyzed by (6) where m and n are arbitrary integer, which decides the extracted watermark bit wi′. Note that Algorithm 3 includes the process to decide existence of a watermark bit when a serial LFSR bit is used. Also, it includes the step to reform the 2D watermark data(6)wi′={0,(2m-1)Δb(u,v)≤ab′′(u,v)<(2m+1)Δb(u,v),1,(2n+1)Δb(u,v)≤ab′′(u,v)<(2n+3)Δb(u,v).Algorithm 3:Watermark extraction procedure
Procedure{Watermark_Extraction}begin{initializeLFSRwith a key(keyembed);for   i=0  to  2m+n-1{if   (LFSRp(i)=``1")  then    {if(⌊(ab′′(u,v)+Δb(u,v)/2)/Δb(u,v)⌋=even)  thenwi′=``0"  by (6);elsewi′=``1"  by (6);  }}initializeLFSRwith key(keyLFSR);for  I=1  to  2m+n-1{xi=zm+n-12m-1+zm+n-22m-2+⋯+zn+121+zn20;yi=zn-12n-1+zn-22n-2+⋯+z121+z020;w′′(xi,yi)=w′(i);}}apply one clock toLFSR;  }end{Watermark_Extraction}The extraction process needs only a few decision tasks so that its speed degradation on the decoding time is negligible, even though the watermark is not necessarily extracted in each decoding process.


## 3. Applying the Proposed Watermarking Scheme

Since the proposed scheme uses the properties of the coefficients in the frequency domain resulting from DCT or DWT and accomplishes the watermarking during scalar quantization, it can be applied into the JPEG/MPEGs or JPEG2000 standards without any modification. It also has inherently an adaptability property for image and video application because it is applicable to a predefined quantizer with any quantizaton step size.All of JPEG and MPEGs use DCT and scalar quantization for intra- or interframes. Thus our scheme is applicable to any of them because ours concerns only with DCT and quantization. To obtain higher robustness in watermarking on a DCT domain, a DC coefficient which is less sensitive to a frequency change is a good candidate for watermarking [8]. Also watermarking in DC coefficients would degrade less image quality than AC coefficients, which was approved by a quantitative analysis [8]. Thus, we apply the proposed watermarking scheme into the DC coefficients after DCT for experimental purpose, without suggesting a new scheme to find the watermarking positions.Each of the resulting sub-bands from DWT in JPEG2000 has the spatial information of the original image as well as the corresponding frequency band information. Thus, differently from DCT, one or a few subbands are usually selected to position the watermark. With considering the human visual system and difference in the quantization step in each subband, we predecided the four lowest sub-bands as the mark space candidates. Then, we performed pre-experiments with about 500 test images to see which sub-band is the robust for attacks. In the experiments, 4-level DWT has been performed and JPEG compressions in various strengths were applied as the attack processes. The experimental results are summarized in Table1. In the table, XYk means a particular sub-band after k-level DWT, where (X∈{L,H}) and (Y∈{L,H}) are the horizontal and vertical tranformation, respectively, with L(H) meaning the result from low- (high-) pass filtering. It shows that the lowest DC subband (LL4) is most robust, but usually it does not quantized. Thus, we chose the next robust subband, LH4, as the watermarking sub-band.Table 1
Subband robustness in JPEG.
JPEG  QualityError ratio (%)LL4LH4HL4HH4120.00.00.00.0100.00.00.00.580.00.30.320.960.03.63.334.342.923.824.755.521.643.048.869.2036.758.265.476.1


## 4. Experimental Result

The proposed embedding/extracting schemes and the arbitrarily assumed positioning schemes were implemented in C++ language on Pentium IV 2.0 GHz CPU. For the test, we used about 500 gray-scale images of pixels in size. Among them, we chose Lena image for demonstration because it contains both low and high frequency components. As the watermark, we used a binary image of512×512 pixels in size which has a special logo for visual confirmation after extracting it. For visibility information we estimated Peak Signal to Noise Ratio (PSNR). For robustness against attacks to an image the error ratios of the extracted watermarks to the original ones were estimated for various malicious and nonmalicious attacks such as JPEG and JPEG2000 compression in different compression ratios, Gaussian noise addition, sharpening, blurring, and various amounts of cropping.Figure2 shows the resulting Lena image example before (31.54 dB in PSNR) and after (31.50 dB) watermarking for JPEG2000, in which the quality degradation (0.04 dB) by watermark is quite negligible. In Table 2, the error ratios of the extracted watermarks after each attack to the images compressed by JPEG or JPEG2000 (J2K) are summarized, where all the ratios are the average values for the 500 test images. It shows that the proposed scheme has an excellent property on robustness for all the considered attacks such that even for the 5% Gaussian noise addition, the error ratio was only 5.5% for JPEG watermarking and 4.7% for JPEG2000 watermarking. In Figure 3, various examples of the extracted watermarks according to their error ratios are shown. As can be  seen in the figures, an watermark with error ratio bigger than 15% is hard to recognize.Table 2
Error ratios resulting from various attacks for JPEG and JPEG2000 watermarking.
AttackError ratio(%)JPEG Quality (%)JPEGJ2KJPEGJPEG2K40600020400002000.8JPEG2000 (bpp)10.300.50.300.250.70Gaussian Noise (%)33.51.755.54.3Sharpening2.20.7Blurring2.71.3Cropping (%)101.51.5153.23.8205.75.0JPEG2000 watermarking example for Lena image: (a) before, (b) after watermarking.
(a)(b)Various examples of extracted watermarks: (a) original watermark, the extracted watermark with error ratio of (b) 1.5%, (c) 5.6%, (d) 10.7%, and (e) 14.2%.
(a)(b)(c)(d)(e)To show the excellence of our scheme, we compared the robustness with the algorithm previously proposed by Seo et al. [4] which is the most similar to ours. The results are shown in Table 3, which includes the JPEG attacks and JPEG2000 attacks. This table shows that for all the attacks ours show 4~5 times better in performance than Yasein's.Table 3
Comparison to Yasein’s scheme.
AttackError ratio (%)Yasein'sOursJPEG quality (%)600040102040.8JPEG2000 (bpp)0.50.500.40.700.2143.5


## 5. Conclusion

In this paper, we proposed an adaptive blind watermark embedding/extracting scheme which is applicable for both JPEG/MPEGs and JPEG2000 standard compression technologies. It uses the properties of the scalar quantization to comply the compression technologies such that a watermark bit is embedded by a value-shift method for the frequency transformed coefficients. Also it includes a scheme to select coefficients in the mark space randomly with a LFSR.Experimental results with about 500 test images showed that the proposed scheme has enough robustness less than the error ratio of 5% and very low visibility of the embedded watermark. Even in comparison with the most similar previous method, ours showed much better performance.Consequently, we expect the proposed scheme to be used as a good watermarking scheme with an appropriate watermark positioning scheme in the application areas that need high invisibility and robustness against various attacks of the embedded watermark.



---

*Source: 348321-2010-05-05.xml*