Keywords

1 Introduction

Nowadays, digital information is largely used due to the ease of storage and transmission. Digitally stored information such as images, audio and video can be copied, edited and shared easily which makes it difficult to identify the ownership of the content. Digital watermarking techniques are developed to address the copyright issue for digital information. In digital image watermarking, an image that represents the owner identity is embedded in the host image. Embedding can be done either in spatial domain or on frequency domain of the host image. The watermark embedding in the spatial domain is considered to be weak against various image processing operations and hence, most of the algorithms are designed to embed the watermark in the frequency domain which is obtained by using transforms such as discrete cosine transforms (DCT) [1–12], discrete Fourier transforms (DFT), and discrete wavelet transforms (DWT). Frequency domain embedding identifies the region of embedding based on the sensitivity of Human Visual System (HVS). The DCT reserves most of the signal information in the low frequency components. Hence, algorithms [9–12] using DCT, embeds the watermark in the middle frequency band to overcome the tradeoff between the robustness and imperceptibility.

In [9], the watermarking algorithm is designed for image content authentication using DCT where the watermark generated from the original image is embedded in middle frequency range. In [10], the DCT coefficients are modified to embed watermark based on the inter-block DCT coefficient correlation. The modification parameter is computed using the DC coefficient and some low frequency coefficient. The scheme proposed in [11], determines the DCT of each 8 × 8 block and computes the complexity of each block by counting the number of nonzero entries in each block. Based on the complexity the blocks are selected and watermark is embedded in the low frequency band of the selected blocks. An algorithm based on Chinese remainder theorem and DCT was proposed in [13]. In [12], sub sampling technique along with Just Noticeable Distortion (JND) function is used for watermarking where the watermark is embedded in middle frequency domain. Some schemes [14, 15] also use the DC coefficients for marking the watermark to improve the robustness.

In [16], using sub sampling four sub images are formed for which DCT is applied. A permutated binary watermark image is embedded into the DCT coefficients of two of the sub images which are selected according to a random coordinates sequence generated by a secret key. This paper proposes a modified version of the embedding technique discussed in [16] and embeds the watermark into non-overlapping blocks of the host image which have permuted pixel values. When DCT is applied to the permuted blocks, the features within the block are uniformly distributed and hence, the watermark can be embedded in any region of the block. This makes the scheme overcomes the restriction of embedding the watermark in the middle frequency band alone. Moreover, based on the size of watermark the watermark can also be embedded more than once.

2 Block Permutation

Most of the watermarking algorithms use the concept of creating blocks from the host image and embedding watermark in it. Here, along with the concept of creating blocks, block permutation is also done before embedding watermark. The embedding algorithm in this paper divides the host image into non overlapping block, permutes the pixel values within blocks and applies DCT for each block separately. The DCT has the property of concentrating the low frequency components in the top left corner which varies diagonally till bottom right corner. The top left most component is the DC coefficient. The remaining components are called AC coefficients. Due to this property of the DCT, embedding the watermark in the low frequency component may result in degradation of the original image whereas the high frequency components may be lost while applying compression functions. Hence, always the middle band serves as the region of embedding. To overcome this restriction, the pixel values within the blocks are permuted and then DCT is applied, which makes the frequency distribution uniform throughout the block. Hence, embedding the watermark in any region has equal chance of being marked in low or high frequency component. Due to this technique the quality of the original image is also maintained up to the desired level as well as the embedding is made robust. The region of embedding is also increased. The permutation technique used in this scheme is first permutating all rows of the block using the function \( t = ((p*s) mod\,D) + 1 \), where D is the number of rows in the block, p is the prime number, s and t are the actual and destination row locations, respectively. The row permuted image is again permuted columnwise using the same function with different prime number. Figure 1 shows the distribution of the DCT block with and without permutation.

Fig. 1
figure 1

a Original image. b DCT of (a). c DCT of permuted image (a)

Full size image

3 Proposed Scheme

Consider a gray scale image, I, of size \( H \times W \), where H and W are height and width of the image, respectively. Let the binary watermark, w be of size \( H_{1} \times W_{1} \), where H 1 and W 1 represents the height and width of the watermark. Since, the watermark is usually much smaller than the host image, it can be embedded using few blocks of the host image and this embedding algorithm requires the host image to be of size \( H \ge 4.H_{1} \) and \( W \ge 4.W_{1} \), which is sufficient to create blocks.

3.1 Watermark Embedding

  1. 1.

    The watermark, w, is scrambled using the standard map (1) with the secret key x 0, \( y_{0} \in [0,2\pi ) \) and the parameter \( |K| > 0 \).

    $$ \left. {\begin{array}{*{20}c} {x_{n + 1} = (x_{n} + y_{n} )\, mod\, 2\pi } \\ {y_{n + 1} = (y_{n} + K.\sin (x_{n + 1} ))\, mod\, 2\pi } \\ \end{array} } \right\} $$
    (1)
  2. 2.

    The scrambled watermark is transformed into a vector, \( w^{'} \) of size \( H_{1} \times W_{1} \).

  3. 3.

    Divide the host image, I, into maximum possible number non-overlapping blocks of sub images B i,j , of size \( BD \times BD \) where \( BD = \hbox{min} (2.H_{1} ,2.W_{1} ) \), \( 1 \le i \le \left\lfloor {\frac{H}{BD}} \right\rfloor \) and \( 1 \le j \le \left\lfloor {\frac{W}{BD}} \right\rfloor \). The part of the image that cannot be divided into blocks of the required size are not used for embedding and are retained as such in the watermarked image.

  4. 4.

    The pixels values within the blocks are permuted using the permutation process discussed in Sect. 2 to make block features uniformly distributed.

  5. 5.

    The permuted blocks rearranged to form a rectangular matrix

    $$ \begin{aligned} & Q = [B_{1,1} ,B_{2,1} , \ldots B_{i,j} ,B_{i + 1,j} ,B_{i,j + 1} ,B_{i + 1,j + 1} \ldots ], \\ & \quad \quad \quad i = 1,3, \ldots ,\frac{H}{BD} - 1,j = 1,3, \ldots ,\frac{W}{BD} - 1 \\ \end{aligned} $$
    (2)
  6. 6.

    In the embedding process, 1/4th of the watermark vector \( w^{'} \) is embedded in each block. Hence, for a single embedding of the watermark vector \( w^{'} \) four blocks from Q are necessary.

  7. 7.

    A random sequence Z = (u, v) with \( 1\, \le \,u,v\, \le \,4 \) of size \( H_{1} \times W_{1} \times \left\lfloor {(size\,of\, Q)/4} \right\rfloor \) is generated. This sequence is used as a coefficient selector during the embedding process.

The steps involved in embedding the watermark vector \( w^{'} \) is as follows:

  1. a.

    Choose first four blocks from the matrix Q defined in (2).

  2. b.

    Apply the DCT for each block separately to obtain the four DCT coefficient sets, D 1, D 2 , D 3 and D 4.

  3. c.

    The watermark is embedded in the DCT coefficient set in the zigzag order leaving the DC coefficient and some of the rows diagonally below the DC coefficient. The watermark bits are embedded starting from the diagonally rth row where \( r = \left\lceil {(BD/t)} \right\rceil \), \( t \in (1,BD - 1) \).

  4. d.

    For the mth bit of the watermark vector \( w^{'} \), i.e. \( w_{m}^{'} \), there are four DCT coefficients in the sets D 1, D 2 , D 3 and D 4 out of which a pair is selected using the coefficient selector, \( Z_{m} = (u,v) \). Within the set D u and D v the mth DCT coefficient in the zigzag order starting from the diagonally rth row is used for embedding. Let it be denoted by V u and V v .

  5. e.

    Now, compare V u and V v . If the bit \( w_{m}^{'} = 1 \) and \( V_{u} < V_{v} \), then swap u and v in Z m . Similarly, if the bit \( w_{m}^{'} = 0 \) and \( V_{u} > V_{v} \), then swap u and v in Z m .

  6. f.

    Using the swapped Z m , reselect V u and V v and compute the following to embed the watermark bit.

    $$ \begin{aligned} & V_{a} = \frac{{|V_{u} | + |V_{v} |}}{2},\,D = \frac{{V_{u} - V_{v} }}{2} \\ & If\, |\frac{D}{{V_{a} }}| \le \beta \\ & \quad V_{u}^{'} = V_{u} + \alpha (2w_{m}^{'} - 1)|V_{a} |;\quad V_{v}^{'} = V_{v} - \alpha (2w_{m}^{'} - 1)|V_{a} | \\ & else \\ & \quad V_{u}^{'} = V_{u} ;\quad V_{v}^{'} = V_{v} \\ \end{aligned} $$

    where \( \alpha \in [0.05,0.1) \), \( \beta = (.1 - a) \times 10 \) and α is the watermark embedding strength and β is the threshold.

  7. g.

    Apply the inverse DCT to the altered set D 1, D 2, D 3 and D 4 and update the modified blocks into the matrix Q.

  8. h.

    Select the next four blocks Q and apply step (b)–step (g), until the number of blocks remaining in Q are less than four or all blocks exhausted.

  9. i.

    The embedded blocks in the rectangular matrix are again replaced to their corresponding positions in the host image.

4 Watermark Detection

Let \( \bar{I} \) be the watermarked image from which the watermark is to be detected. From the image \( \bar{I} \) the rectangular matrix Q is created as in embedding process. The swapped coefficient selector Z = (u, v) obtained during embedding process is used for watermark detection.

  1. a.

    Choose first four blocks from the matrix Q formed from \( \bar{I} \).

  2. b.

    Apply the DCT for each block separately to obtain the four DCT coefficient sets, \( \bar{D}_{1} ,\bar{D}_{2} ,\bar{D}_{3} \) and \( \bar{D}_{4} \).

  3. c.

    The watermark bits are extracted from the DCT coefficient set in the zigzag same as in embedding process. The mth bit of the extraction vector \( \bar{w}^{'} \), i.e. \( \bar{w}_{m}^{'} \), is determined using the DCT coefficients V u and V v selected using the swapped coefficient selector \( Z_{m} = (u,v) \).

    $$ \bar{w}_{m}^{'} = \left\{ {\begin{array}{*{20}c} {1,} & {if\, V_{u} \ge V_{v} ,} \\ {0,} & {if\, V_{u} < V_{v} .} \\ \end{array} } \right. $$
  4. d.

    The extraction vector is converted into a two dimensional array of size \( H_{1} \times W_{1} \), for which inverse permutation is applied using the standard map with same key. The image produced is the watermark \( \bar{w} \), that is embedded the set of blocks.

  5. e.

    The Normalised Correlation (NC) of the extracted watermark is computed using formula (3) given below.

    $$ NC = \frac{{\sum\nolimits_{i} {\sum\nolimits_{j} {w(i,j) \cdot \bar{w}(i,j)} } }}{{\sum\nolimits_{i} {\sum\nolimits_{j} {[w(i,j)]^{2} } } }} $$
    (3)

    where w(i, j) and \( \bar{w}(i,j) \) represents the (i, j)th pixel value in the original watermark and extracted watermark, respectively.

  6. f.

    Select the next four blocks Q and apply step (b)–step (e), until the number of blocks remaining in Q are less than four or all blocks exhausted.

  7. g.

    Finally, using \( \bar{w} \) and their corresponding NC from each block the extracted watermark w e is obtained by taking weighted average as given in (4).

    $$ w_{e} = \sum\limits_{i} \frac{NC(i)}{Total}*\bar{w}_{i} $$
    (4)

    where NC(i) is the normalized correlation of ith extracted watermark, Total is the sum of \( NC^{\prime}s \) of all extracted watermark and \( \bar{w}_{i} \) is the ith extracted watermark from the blocks.

5 Experimental Results

The proposed scheme is tested using a gray scale image of size \( 512 \times 512 \) and a binary watermark of size \( 64 \times 64 \). The performance of the scheme is analysed using two types of measure: peak signal to noise ratio (PSNR) and normalized correlation (NC). PSNR is used to test the quality of the watermarked image against the original image. For the 8 bit gray scale image the PSNR is computed using formula (5):

$$ PSNR(dB) = 10.\mathop {\log }\nolimits_{10} \left(\frac{{255^{2} }}{MSE}\right) $$
(5)

where \( MSE = \frac{1}{D \times D}\sum\nolimits_{i} \sum\nolimits_{j} [I(i,j) - \bar{I}(i,j)]^{2} \), I and \( \bar{I} \) are the original and watermarked image. Figure 2 shows the original image, marked image and extracted watermark. The PSNR value of the marked image is 55.8328 dB for \( \alpha = .09 \) and \( t = 1.5 \) which is sufficiently more than the desired value of 30 dB to make watermark imperceptible. The NC gives the correlation between the original and extracted watermark and it is 1 for Fig. 2c. Hence, the extracted watermark is same as the original one.

Fig. 2
figure 2

a Original image. b Watermarked image with t = 1.5 (PSNR = 56.1787 dB). c Extracted watermark (NC = 1)

Full size image

The comparison of the proposed scheme with and without block permutation is given in Table 1. From the table, it is clear that the detection of the watermark under various attack is equally good irrespective of the region of embedding when embedded in permuted blocks whereas without permutation the performance of the scheme varies when embedded in different region. Moreover, when watermark is embedded without permuting values in the block, the PSNR and NC values in the table shows, the quality of the watermark extracted from middle frequency region is low when compared to low frequency region. Table 1 also shows the comparison of the scheme with [16]. From the NCs of extracted watermark without permutation \( (t = 127) \) and that of [16], it can be seen that multiple embedding and weighted average improves the performance of the extraction process. From the table, it is also clear that the proposed scheme preforms better than [16] under most of the attacks and in some cases it is equally good.

Table 1 Comparison of the proposed scheme with [16] (t = 127 and t = 3 represents the low and middle frequency regions, respectively)
Full size table

The algorithm is tested against various attacks such as jpeg compression, cropping, and by applying various noises and filters. The results are compared with [10] in Table 2, which shows that the performance is good against attacks such as cropping and jpeg compression whereas for other attacks the results show it is resistant against these attack. Figure 3 shows the results of the cropping attack where it can be seen that the extracted watermark is same as original watermark. The watermark extracted after distorting the watermarked image under various attacks is given in Fig. 4.

Table 2 Comparison of the proposed scheme (t = 127) with [10] under various attacks
Full size table
Fig. 3
figure 3

The cropped images and the corresponding extracted watermark

Full size image
Fig. 4
figure 4

The extracted watermark after a Salt and Pepper noise (0.01). b White Gaussian noise, mean = 0, variance = 0.001. c Median filter (3 × 3). d Histogram equalization

Full size image

6 Conclusion

This paper introduces the techniques of embedding the watermark in the DCT of the permuted block. A watermarking scheme is proposed based on this technique. The simulation results show that embedding the watermark after permutation performs alike irrespective of the region of embedding. This overcome the restriction in selecting the region of embedding watermark and increases the region of embedding. Moreover, the performance of the scheme against JPEG compression, cropping, Gaussian noise, salt and pepper noise and median filter is equally good when compared with the existing schemes.