Digital Watermarking Scheme Enhancing the Robustness Against Cropping Attack

Abstract

Most digital watermarking schemes using QR factorization suffer from being unable to fully utilize the elements of the R matrix. Thus, these schemes are neither secure nor robust to resist the cropping attack. Besides, these schemes do not deal with the allowable modification ranges of the R elements, thereby causing the damage to the hidden watermark. In this paper, we designed an algorithm to redundantly embed the four copies of the watermark bits to enhance the ability to against the cropping attack. During the embedding process, the property of sign wave is employed to ease the modification of real number coefficients. After the four copies of a watermark bit are extracted, they may be different due to possible attacks. Therefore, we designed a weighted strategy to resolve the watermark bit. The experimental results show that our scheme satisfy the requirements of imperceptibility and robustness. Particularly, our scheme has prominent robustness against cropping attacks.

1 Introduction

Digital watermarking is a common way to protect digital images. The digital image is watermarked with a watermark, which may be a binary image or just a binary stream. Depending on the purpose of the watermarking scheme, the watermark is either robust or fragile. The purpose of a robust watermarking scheme is to protect the copyright of the digital image. The copyright of the digital image is proved by the extracted watermark, so the extracted watermark should be robust enough even if the watermarked image undergoes slight modification. On the other hand, the purpose of a fragile watermarking scheme is to protect the integrity of the digital image. The extracted watermark should be fragile when the watermarked image has been tampered with. The working domain of the digital images may be spatial or frequent [5]. Recently, some researches tried to work on another domain which is derived from matrix factorization, such as SVD [1, 2, 8], QR decomposition, or LU decomposition. The main idea is to utilize matrix factorization to decompose the image and embed the watermark into one of the decomposed matrices. Among these matrix factorization methods, QR decomposition is a good choice for digital watermarking and image steganography. The reasons are as follows. Firstly, in comparison with SVD, QR decomposition has lower computational complexity and can avoid false positive problems [12, 14]. Secondly, in comparison with LU factorization, QR decomposition is more accurate for least square problems. Thirdly, LU factorization can only applied to square matrices while QR decomposition can be applied to rectangular and square matrices. Fourthly, the first row elements of the R matrix obtained by QR decomposition are able to resist to several image processing operations, such as lossy compression, noise addition, and filtering. Finally, the first row elements of the R matrix are likely to be greater than those elements in other rows, thereby allowing a greater modification range [12, 14]. Because of the above mentioned properties of QR decomposition, some researches use the first row elements for watermark embedding and image steganography [4, 7, 11,12,13,14].

Most QR-based digital watermarking schemes suffer from being unable to fully utilize the coefficients of the R matrix. Therefore, such methods may have low data hiding capacity and watermark security. For example. Su et al. [12] adopted QR decomposition to hide a robust color watermark into a color image. They use the last element of the first row in the R matrix to hide a watermark bit, but the allowable modification range of this coefficient was not discussed. Thus, the embedded watermark may be damaged by the reverse QR decomposition without any image processing operation or any malicious attack. This problem also occurs in Subhedar and Mankar’s image steganography scheme [14]. The main concern of a QR-based digital watermarking scheme is that the modification to the decomposed matrix may cause the pixel values out of range. In order to fully utilize all the coefficients in the R matrix, we have to know the allowable modification range of each coefficients.

To cope with this issue, we have built formulas to compute the allowable modification ranges, thereby increasing the capability of information hiding and watermark security [6]. Our watermark embedding scheme employ the sine wave function in trigonometry and achieve the possible minimal modification within the allowable bounds. The sign wave simplifies the modification to real number coefficients by its nature. Like Su et al.’s scheme [12], the host image is decomposed by QR decomposition, and the watermark is embedded in the R matrix. But unlike their scheme, we use all elements of the first row of matrix R and adopt Householder reflections [15] for QR decomposition because it is numerical stable relative to Gram-Schmidt process [3, 10], which is adopted by Su et al.’s scheme [12]. In addition, most QR-based watermarking scheme embeds one watermark bit in an image block; therefore, their watermarks are prone to be fragile to cropping attacks. Take the example of Su et al.’s scheme. When the watermarked image is cut 25% off, the correct rate of the extracted watermark is about 87.75%. However, when the watermarked image is cut 50%, the correct rate of the extracted watermark decreases to 62.64% [12]. Therefore, we design an embedding strategy to enhance the robustness against cropping attacks. The rest of this paper is organized as follows. In Sect. 2, we will analyze the allowable modified ranges of the elements and explain the watermark embedding and extraction scheme in detail. In Sect. 3, we will demonstrate the experimental results and give some discussions. Finally, we will give conclusions in Sect. 4.

2 The Proposed Scheme

2.1 The Allowable Modification Range

Suppose the host image is a gray-level image. Thus, the integer pixel values of the host image range from 0 to 255. In this research, 4 × 4 image blocks are used to embed watermark. Thus, the matrix A is denoted as a 4 × 4 matrix. Each matrix A is factorized to matrix Q and R via QR decomposition, which are illustrated as follows:

$$ A = \left[ {\begin{array}{*{20}c} {a_{00} } & {a_{01} } & {a_{02} } & {a_{03} } \\ {a_{10} } & {a_{11} } & {a_{12} } & {a_{13} } \\ {a_{20} } & {a_{21} } & {a_{22} } & {a_{23} } \\ {a_{30} } & {a_{31} } & {a_{32} } & {a_{33} } \\ \end{array} } \right],\,Q = \left[ {\begin{array}{*{20}c} {q_{00} } & {q_{01} } & {q_{02} } & {q_{03} } \\ {q_{10} } & {q_{11} } & {q_{12} } & {q_{13} } \\ {q_{20} } & {q_{21} } & {q_{22} } & {q_{23} } \\ {q_{30} } & {q_{31} } & {q_{32} } & {q_{33} } \\ \end{array} } \right],\,{\text{and}}\,R = \left[ {\begin{array}{*{20}c} {r_{00} } & {r_{01} } & {r_{02} } & {r_{03} } \\ 0 & {r_{11} } & {r_{12} } & {r_{13} } \\ 0 & 0 & {r_{22} } & {r_{23} } \\ 0 & 0 & 0 & {r_{33} } \\ \end{array} } \right] $$

If the modification applies to the first row elements of the R matrix, then the reconstructed values in matrix A should also range from 0 to 255. Thus, the allowable modification range of the R matrix should be identified to accommodate the valid pixel values. For x = R[0, j], where j = 0..3, we define the allowable upper bound ub and lower bound lb of the modified x by Eqs. (1) and (2) [6].

$$ lb = \mathop {\hbox{max} }\limits_{{i \in \left\{ {0..3} \right\}}} \left( {LB\left[ i \right]} \right) $$

(1)

And

$$ ub = \mathop {\hbox{min} }\limits_{{i \in \left\{ {0..3} \right\}}} \left( {UB\left[ i \right]} \right) $$

(2)

where

$$ LB[i] = \left\{ {\begin{array}{*{20}l} { - \infty } \hfill & {{\text{if}}\,Q[i ,0] = 0,} \hfill \\ {\hbox{min} \left( {a, b} \right)} \hfill & {{\text{otherwise}} .} \hfill \\ \end{array} } \right. $$

(3)

$$ UB[i] = \left\{ {\begin{array}{*{20}l} \infty \hfill & {{\text{if}}\,Q[i ,0] = 0,} \hfill \\ {\hbox{max} \left( {a, b} \right)} \hfill & {{\text{otherwise}} .} \hfill \\ \end{array} } \right. $$

(4)

$$ a = R[0 ,j] - {{A[i ,j]} \mathord{\left/ {\vphantom {{A[i ,j]} {Q[i ,0]}}} \right. \kern-0pt} {Q[i ,0]}} $$

(5)

and

$$ b = R[0 ,j] + \left( {255 - {{A[i ,j]} \mathord{\left/ {\vphantom {{A[i ,j]} {Q[i ,0]}}} \right. \kern-0pt} {Q[i ,0]}}} \right). $$

(6)

2.2 Watermark Embedding

Suppose that the host image is an $M \times N$ gray-level image and the watermark is an $M/4 \times N/4$ binary image, where both M and N are multiples of four. At first, the host image is divided into n non-overlapping $4 \times 4$ blocks, where $n = M/4 \times N/4$. Then, each block A, which can be seen as a $4 \times 4$ matrix, is factorized to Q and R matrices by means of Householder reflections, and all R matrices are used to embed the watermark. Let $W = (w_{0} ,w_{1} , \ldots ,w_{n - 1} )$ denote the binary watermark, where $w_{i} \in \left\{ {0, \, 1} \right\}$ for $i = 0,1, \ldots n - 1$. Let $(R_{0} ,R_{1} , \ldots ,R_{n - 1} )$ denote the array of n R matrices constructed from the n image blocks. For the sake of increasing the survival of the watermark, we adopt a two-pronged strategy. Firstly, the original array $(R_{0} ,R_{1} , \ldots ,R_{n - 1} )$ is shuffled according to a pseudo-random number generator seeded by the secret key SK. Secondly, four copies of each watermark bit are redundantly inserted into the first row elements of the R matrix. Let $(R_{0}^{{\prime }} ,R_{1}^{{\prime }} , \ldots ,R_{n - 1}^{{\prime }} )$ denote the shuffled array, and $R_{i} \left[ {0,0} \right]$, $R_{i} \left[ {0,1} \right]$, $R_{i} \left[ {0,2} \right]$, and $R_{i} \left[ {0,3} \right]$ respectively denote the first row elements of $R_{i}$, for $i = 0..(n - 1)$. To embed a watermark bit w _i , the four copies of w _i are redundantly inserted into the four R elements: $R_{{i\,\text{mod}\,n}}^{\prime } \left[ {0,0} \right],R_{{i + 1\,\text{mod}\,n}}^{\prime } \left[ {0,1} \right],R_{{i + 2\,\text{mod}\,n}}^{\prime } \left[ {0,2} \right],\;{\text{and}}\;R_{{i + 3\,\text{mod}\,n}}^{\prime } \left[ {0,3} \right]$. Finally, the reverse operation of the QR decomposition is used to generate the watermarked image.

The rule for embedding a watermark bit $w \in \left\{ {0,1} \right\}$ to an element x of a matrix R depends on a sine wave function:

$$ f\left( x \right) = sin(k \cdot x), $$

(7)

where $k > 0$ and is a real number. Accordingly, the wavelength λ of the function f is (360/k). If $w = 1$, then x is modified to $x^{{\prime }}$ such that $f(x^{{\prime }} ) \ge 0$; otherwise, if $w = 0$, then x is modified to $x^{{\prime }}$ such that $f(x^{{\prime }} ) < 0$. Note that the modification of x to x′ is restricted to the following three constraints:

• 1. The range of x′ needs to be within [0, 255].

• 2. The modification of x should be as less as possible so that $x^{{\prime }}$ is near to x to ensure the imperceptibility of our scheme.

• 3. The value of $|f(x^{{\prime }} )|$ should be as large as possible, hence our scheme can tolerate an acceptable alteration on the watermarked image.

Therefore, the proposed scheme follows the three steps below to modify x.

• Step 1: For $x = R\left[ {0,j} \right]$, where $j = 0..3$, define the allowable upper bound ub and lower bound lb of $x^{{\prime }}$ by Eqs. (1) and (2).

• Step 2: Complying with the following rules, modify x to $x^{{\prime }}$ such that $|f(x^{{\prime }} )| = 1$ and the difference between x and x′ is as small as possible.

  Rules for w = 0:

  • If $(x \ge 0 \wedge r \le 0.25\lambda )$ then $x^{{\prime }} = (x - r) - 0.25\lambda$.

  • If $(x \ge 0 \wedge r > 0.25\lambda )$ then $x^{{\prime }} = (x - r) - 0.75\lambda$.

  • If $(x < 0 \wedge r \ge - 0.5\lambda )$ then $x^{{\prime }} = (x - r) - 0.25\lambda$.

  • If $(x < 0 \wedge r < - 0.5\lambda )$ then $x^{{\prime }} = (x - r) - 1.25\lambda$.

  Rules for w = 1:

  • If $(x \ge 0 \wedge r \le 0.75\lambda )$ then $x^{{\prime }} = (x - r) + 0.25\lambda$.

  • If $(x \ge 0 \wedge r > 0.75\lambda )$ then $x^{{\prime }} = (x - r) + 1.25\lambda$.

  • If $(x < 0 \wedge r \ge - 0.25\lambda )$ then $x^{{\prime }} = (x - r) + 0.25\lambda$.

  • If $(x < 0 \wedge r < - 0.25\lambda )$ then $x^{{\prime }} = (x - r) - 0.75\lambda$.

  The remainder r of x divided by λ is defined by

  $$ r = s\left( {\left| x \right| - \lambda \left\lfloor {\frac{\left| x \right|}{\lambda }} \right\rfloor } \right), $$

  (8)

  where $s \in \{ 1, - 1\}$ represents the sign of x.

• Step 3: If $x^{{\prime }}$ is out of allowable range, perform the following procedure to adjust $x^{{\prime }}$ so that $x^{{\prime }}$ is able to be within $\left[ {lb,ub} \right]$, the difference between x and $x^{{\prime }}$ is as close as possible, and $\left| {f\left( {x^{{\prime }} } \right)} \right|$ is as large as possible.

2.3 Watermark Extraction

To extract the robust watermark W, the secret key SK is used to generate the shuffled array $(R_{0}^{{\prime }} ,R_{1}^{{\prime }} , \ldots ,R_{n - 1}^{{\prime }} )$. In principle, the extracted bit $w^{\prime }$ of an element of the R matrix is determined according to Eq. (9).

$$ w^{{\prime }} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\,f(x) \ge 0,} \hfill \\ 0 \hfill & {{\text{otherwise}} .} \hfill \\ \end{array} } \right. $$

(9)

where x = R[0, j] for j = 0..3.

Remember that each watermark bit is redundantly embedded in four elements of the R matrix. Therefore, the four copies of the watermark bit w _i are extracted from coefficients $R_{{i\,\text{mod}\,n}}^{\prime } \left[ {0,0} \right],R_{{i + 1\,\text{mod}\,n}}^{\prime } \left[ {0,1} \right],R_{{i + 2\,\text{mod}\,n}}^{\prime } \left[ {0,2} \right],\;{\text{and}}\;R_{{i + 3\,\text{mod}\,n}}^{\prime } \left[ {0,3} \right]$, and each copy is determined by Eq. (9). Note that the extracted four copies may be different due to the possible alteration to the watermarked image, it is necessary to have a rule to reach a consensus about the extracted watermark bit $w_{i}^{\prime }$. Intuitively, the majority voting principle is practical. That is, if two or more copies are ‘1’, then the extracted watermark bit $w_{i}^{\prime }$ is determined as ‘1’; otherwise, the extracted watermark bit $w_{i}^{\prime }$ is determined as ‘0’. Because different elements of the R matrix may have different ability to resist image processing operations or malicious attacks [12], more sophisticated way can be used, which puts different weights on the four extracted copies. Assume that the ability to resist image processing operations of the R element r_0i is weighted as α _j , for j = 0, 1, 2, 3 and

$$ \sum\limits_{j = 0}^{3} {\alpha_{j} = 1} $$

Also assume that c _i (0), c _i (1), c _i (2), and c _i (3) are the extracted four copies of the watermark bit w _i . Then, the extracted watermark bit $w_{i}^{\prime }$ is determined according to the following rule.

$$ w_{i}^{{\prime }} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if }}\,\sum\limits_{j = 0}^{3} {\alpha_{j} \cdot c_{i} } (j) \ge 0.5,} \hfill \\ 0 \hfill & {{\text{otherwise}} .} \hfill \\ \end{array} } \right. $$

(10)

In fact, the majority voting principle is a special case of the weighted scheme. Generally, the weight α _j can be determined according experimental analysis.

3 Experiment Results and Discussions

In general, a robust watermarking scheme is evaluated by its imperceptibility and robustness. The imperceptibility means that the difference between the host image and the watermarked image should not be perceived by human eyes, and the robustness means that the extracted watermark should be similar to the original watermark. In this paper, we use PSNR to evaluate the imperceptibility of our scheme [9].

$$ PSNR = 10 \times \,\log \frac{{255^{2} }}{MSE}, $$

(11)

where

$$ MSE = \frac{1}{M \times N}\sum\limits_{i = 1}^{M} {\sum\limits_{j = 1}^{N} {(p_{i,j} - p_{i,j}^{{\prime }} )^{2} } } . $$

(12)

The notation M and N in Eq. (12) denote the width and height of an image, respectively, and p_i,j and $p_{i,j}^{\prime }$ denote the pixel of the original and watermarked image, respectively. Generally, the difference between the watermarked image and the host image is visually imperceptible if PSNR is greater than 30. The robustness is evaluated by the indicator NC as follows.

$$ NC = \frac{1}{W \times H}\sum\limits_{i = 1}^{W} {\sum\limits_{j = 1}^{H} {(\overline{{w_{i,j} \oplus w_{i,j}^{{\prime }} }} )} } $$

(13)

The notation W and H in Eq. (13) denote the width and height of the watermark image, respectively, w_i,j and $w_{i,j}^{\prime }$ denote the bit of the original and extracted watermark, respectively, and ‘⊕’ represents the logical XOR operation. The larger the NC is, the more robust the extracted watermark is.

Figure 1(a) is our watermark, which is embedded into the host image (Fig. 1(b)). The embedding rule (Eq. (7)) needs a parameter k, but it is not necessary to use the same value of k for each element of the R matrix to embed a bit. In this experiment, we use four values (10, 90, 90, 90, 90) respectively corresponding to the four elements (R[0,0], R[0,1], R[0,2], R[0,3]). Figure 1(c) is the watermarked image, and the PSNR is 38.0081. Obviously, our scheme is qualified for the imperceptibility. With regard to the robustness, we simulate two kinds of attacks, namely cropping and JPEG lossy compression, on the watermarked image and inspect the survival of the extracted watermark. As mentioned in the above section, we can use a set of weights (α₀, α₁, α₂, α₃) for the extracted four copies to determine the extracted watermark bit. In this experiment, we test two different sets (1.0, 0.0, 0.0, 0.0) and (0.25, 0.25, 0.25, 0.25) on the robustness of the watermark.

Fig. 1.

The watermark, the host and watermarked images

We performed experiments on the watermarked image under cropping attack with different cropping ratios (CR) from 0.05 to 1.00. Figure 2(a)–(t) are the extracted watermarks and their respective NC values, and the corresponding cropping ratios are listed as well. Figure 2 shows that the similarity between the extracted watermark and the original watermark is greater than 80% even though the cropping ratio reaches as high as 0.6. Compared to the NC value against the attack with 25% cropping ratio of Su et al.’s scheme [12], our scheme gets 97.81%, which is higher than Su et al.’s 87.7%. When the watermarked image is cut 50% off, the NC value of our scheme is 88.59% while that of Su et al.’s is 62.64%. Thus it can be seen that our embedding strategy largely enhances the robustness against cropping attacks. The other experiments were performed on the watermarked image under JPEG lossy compression with different compression qualities, i.e. compressed image quality, from 0.05 to 1.00. The compression is implemented with Java Image I/O API provided in Java SE 8. Figure 3(a)–(t) are the extracted watermarks and their respective NC values, and the corresponding JPEG qualities are listed as well. Figure 3 shows that the similarity between he extracted watermark and the original watermark is greater than 80% even though the compression quality decreases as low as 0.45.

Fig. 2.

The NC values of extracted watermarks for cropped images with different cropping ratio values.

Fig. 3.

The NC values of extracted watermarks for JPEG compressed images with different quality values

We have mentioned earlier that two sets of weights are used to test the robustness of the watermark. Actually, different weights have different effects on the robustness of the watermark. Figure 4(a) demonstrates the correlations between the NC values and cropping ratios, and Fig. 4(b) demonstrates the correlations between the NC values and JPEG compression qualities. It is observed that the two weights perform vary and each has its own strengths. The set with equal weights outperforms the set (1.0, 0.0, 0.0, 0.0) on extracting watermarks from cropped watermarked images; on the contrary, the set (1.0, 0.0, 0.0, 0.0) outperforms the extracting scheme with equal weights on extracting watermarks from compressed watermarked image. Accordingly, the set with equal weights is suitable for being against the alterations that concentrates in a region. The set (1.0, 0.0, 0.0, 0.0) means that the decision of the extracted watermark bit depends on the first element only and is suitable for being against the alterations that spread over the watermarked image. This distinct fact gives our scheme flexibility. We can juxtapose the watermarks extracted by our scheme with different weights and display the best one. Correspondingly, Fig. 2 shows the extracted watermarks with the weights (0.25, 0.25, 0.25, 0.25), and Fig. 3 shows the extracted watermarks with weights (1.0, 0.0, 0.0, 0.0).

Fig. 4.

The NC values relative to different parameters

4 Conclusions

Most QR-based digital watermarking schemes suffer from being unable to fully utilize the coefficients of the R matrix. Therefore, such methods may have low data hiding capacity and watermark security. To cope with this issue, we have built formulas to compute the allowable modification ranges and employ the sine wave function in trigonometry and achieve the possible minimal modification within the allowable bounds. In the embedding scheme, the host image is decomposed by QR decomposition, and each watermark bit is redundantly embedded in the R matrix. We adopt Householder reflections for QR decomposition because it is numerical stable relative to Gram-Schmidt process. Redundantly embedding a watermark bit can increase the robustness and security of our scheme. Observing from the experiment results, our scheme indeed succeeds in enhancing the robustness against cropping attacks However, after the four copies of a watermark bit are extracted, they may be different due to possible attacks. Therefore, we design a weighted strategy to resolve the watermark bit. The experimental results show that our scheme satisfy the requirements of imperceptibility and robustness. In the future, we will test more sets of weights on extracting the watermark and give analysis of the relationship between the set of weights and the type of attacks.