# Reversible Image Watermarking Algorithm Based on Quadratic Difference Expansion

Authors: Zhengwei Zhang; Mingjian Zhang; Liuyang Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

To improve the visual quality and embedding rate of existing reversible image watermarking algorithms, a reversible image watermarking algorithm based on quadratic difference expansion is proposed. First, the pixel points with grayscale values 0 and 255 in the original image are removed, and then, the half-scrambled watermark information is embedded into the original image using linear difference expansion. Finally, the remaining half of the watermark information is embedded into the previously generated watermarked image by the quadratic difference expansion, meanwhile the removed pixel points with grayscale values 0 and 255 in the image are merged, and the final watermarked image is generated accordingly. The experimental results show that the algorithm has both a high embedding rate and a high visual quality, which can completely recover the original image. Compared with other difference expansion watermarking algorithms, it has certain advantages without having to consider the smoothness of the embedded image region.


---

## Body

## 1. Introduction

Digital watermarking is an important branch of information hiding technology. Information hiding technology studies how to hide secret information in public information. It can be divided into steganography and digital watermarking technology. The digital watermarking is an important means of copyright protection. Its basic principle is a technology of embedding identification information directly into digital multimedia by using redundant data and randomness which are ubiquitous in digital multimedia works. The reversible watermarking is a special application of digital watermarking.Reversible image watermarking embeds the information into the carrier image on the premise of ensuring the visual quality [1]. The purpose is to losslessly reconstruct the host image after the watermark is extracted. Therefore, compared with the traditional watermarking methods, the amount of embedding information is more demanding; hence, it has more extensive research and application value in the fields of judicial, military, medical, and other fields which ask for high-image authenticity and integrity. The basic goal of the reversible image watermarking algorithms study is to achieve the maximum embedding capacity of effective information with less distortion [2].The large-capacity reversible watermarking algorithm based on the difference expansion of adjacent pixels proposed by Tian [3] has caught increasing attention. The method is to calculate the mean and difference of the selected pairs of adjacent pixels. The difference is expanded through a pixel pair to embed the watermark. On the basis of Tian’s algorithm, Alattar [4] proposed a generalized integer wavelet transform reversible watermarking algorithm. The adjacent pixels are selected as a transform unit for watermark embedding. The capacity of embedding watermark information via Alattar’s method can be up to 1.5 times that of the Tian’s, and the embedding capacity is larger.For the difference expansion embedding method, the overflow location map is an important factor affecting the embedding capacity. Eliminating the location map is extremely important for improving the performance of the algorithm. In the literature [5], a reversible watermarking algorithm combining difference expansion and reversible comparison graph was proposed to divide the image into mutually disjoint 2×2 image blocks. In each image block, the first two pixels were reversible contrast image pixel pairs and the other two pixels were difference expansion pixel pairs, both of which were used to embed information. The reversible contrast image pixel pairs were mainly used to embed little additional information to replace the location map, and the embedding capacity was greatly improved. However, half of the pixel pairs adopted a reversible contrast map transformation, and the image quality was seriously degraded. In the literature [6], a reversible embedding method based on difference histogram translation was proposed. To avoid pixel overflow, the pixel value was adjusted to a certain range before translation and the position of the adjustment pixel was recorded in the location map. This embedding method was quite unique in terms of overflow handle, but it still needed to embed a compressed location map.The literature [7] proposed a reversible image watermarking algorithm which combined the difference expansion and LSB. It achieved a large embedding capacity and good visual quality. Lin et al. [8] proposed a reversible watermarking algorithm that combined histogram translation and prediction difference to expand the embedding capacity and achieved good results.In this paper, a reversible image watermarking algorithm based on quadratic difference expansion is proposed, which uses the difference expansion algorithm to embed the watermark twice, without considering the overflow location map that may occupy effective space and the smoothness of the embedded image region; accordingly, the embedding capacity is increased and the visual quality is improved. Experimental results indicate that the algorithm not only has a high embedding rate but also has a high visual quality and completely restores the original image.


## 2. Quadratic Difference Expansion Algorithm

The difference expansion algorithm based on adjacent pixel pairs proposed by Tian [3] performs integer transform on any pixel pair P = (x, y) in the image to obtain the mean l and the difference h. Accordingly, the l and h are inversely transformed and can losslessly recover the original image pixel pair values x and y.Positive transform is as follows:(1)l=x+y2,h=x−y.Inverse transform is as follows:(2)x′=l+h′+12,y′=l−h′2.The obtainedh is shifted to the left by 1 bit, and the watermark b is embedded in its least significant bit, which is the difference expansion, and its mathematical expression is h′=2h+b.Using the difference expansion to embed the watermark information to obtain the pixel value may cause the pixel overflow, so thex′ and y′ obtained by the inverse transform should be limited to the range [0, 255]; otherwise, it will not be reversible. Therefore, it is necessary to limit h′:(3)h′≤min2255−l,2l+1.The difference expansion watermarking algorithm uses the difference of pixel pairs to perform watermark embedding, and its embedding capacity is limited.To improve the watermark embedding capacity and the visual quality, the pixel pair (x′, y′) generated by the difference transform is used again to perform the quadratic watermark embedding using difference expansion. The specific process is as follows:(4)l′=x′+y′2,h″=x′−y′,h‴=h″2+b.Inverse transform is as follows:(5)x″=l′+h‴+12,y″=l′−h‴2.The watermarked image generated by embedding the watermark after linear difference expansion may overflow, but after the quadratic difference expansion, it returns to the original image.The specific implementation process of the quadratic difference expansion watermarking algorithm is as follows.Assuming that the initial pixel pairP = (x, y), the linear difference expansion is embedded with a watermark bit value of b, and the quadratic difference expansion is embedded with the watermark bit value of b′; then,(6)x′=x+y2+2x−2y+1+b2,y′=x+y2−2x−2y+b2,l=x′+y′2=x+y/2+2x−2y+1+b/2+x+y/2−2x−2y+b/22,h=x′−y′=2x−2y+1+b2+2x−2y+b2,h′=2x−2y+1+b/2+2x−2y+b/22+b′,x″=x+y/2+2x−2y+1+b/2+x+y/2−2x−2y+b/22+2x−2y+1+b/2+2x−2y+b/2/2+b′+12,y″=x+y/2+2x−2y+1+b/2+x+y/2−2x−2y+b/22−2x−2y+1+b/2+2x−2y+b/2/2+b′2.Depending on the watermark embedding value, the new image pixel pair value (x″,y″) and the original image pixel pair value (x, y) are also different.When the embedded watermark informationb = 1, b′ = 1.If one of the pixel pair (x, y) is odd and the other is even,(7)x″=x+y2+x−y2+1=x−1+1=x,y″=x+y2−x−y+12=x+y2−12−x−y+12=y−1.If in the pixel pair (x, y), both are odd or even,(8)x″=x+y+12+x−y+22=x+y2+x−y2+1=x+1,y″=x+y+12−x−y+12=x+y2−x−y2=y.When the embedded watermark informationb = 1, b′ = 0.If one of the pixel pair (x, y) is odd and the other is even,(9)x″=x+y2+x−y+12=x+y2−12+x−y+12=x,y″=x+y2−x−y2=x+y2−12−x−y2+12=y.If in the pixel pair (x, y), both are odd or even,(10)x″=x+y+12+x−y+12=x+y2+x−y2=x,y″=x+y+12−x−y2=x+y2−x−y2=y.When the embedded watermark informationb = 0, b′ = 1.If one of the pixel pair (x, y) is odd and the other is even,(11)x″=x+y−12+x−y+22=x+y−12+x−y−12+1=x,y″=x+y−12−x−y+12=x+y−12−x−y+12=y−1.If in the pixel pair (x, y), both are odd or even,(12)x″=x+y2+x−y+22=x+y2+x−y2+1=x+1,y″=x+y2−x−y+12=x+y2−x−y2=y.When the embedded watermark informationb = 0, b′ = 0.If one of the pixel pair (x, y) is odd and the other is even,(13)x″=x+y−12+x−y+12=x+y−12+x−y+12=x,y″=x+y−12−x−y2=x+y−12−x−y−12=y.If in the pixel pair (x, y), both are odd or even,(14)x″=x+y2+x−y+12=x+y2+x−y2=x,y″=x+y2−x−y2=x+y2−x−y2=y.Regardless of the embedded watermarkb and b′, the generated new image pixel pair value (x″, y″) and the original image pixel pair value (x, y) are equivalent in most cases, but there are very few cases that x″ is 1 greater than x or y″ is 1 less than y, so in this paper, when embedding the watermark using quadratic difference expansion, in order to avoid overflow, it is necessary to first remove the pixel points of the original image with pixel values of 0 and 255.


## 3. Watermark Embedding

The process of watermark embedding is shown in Figure1, and the specific operation process is as follows:(1)
Make an Arnold transform on the watermarkW to get W′. The W′ is transformed into a one-dimensional binary sequence.To enhance the robustness and security of digital image watermarking, the traditional Arnold scrambling transform is improved [9]. This improved method is as follows:(15)x′y′=1112c2111dxymodMx′,y′∈0,1,2,…,N−1,where, (x′,y′) is the transformed pixel coordinate, (x, y) is the original pixel coordinate, M is the image size, and c and d are the scrambling numbers. The Arnold transform is one-to-one mapped, and the parameters c and d are randomly generated.(2)
Remove the pixel points with grayscale values 0 and 255 in the original image to avoid overflow when the watermark is embedded, and send the removed pixel points with grayscale values 0 and 255 to the receiver as a zero watermark so as not to use when extracting it.(3)
From left to right and from top to bottom, take two pixels in order (the number of the selected pixel pair and the half of the watermark to be embedded are equal). Carry out the difference expansion based on the embedded watermark capacity (the first half of the watermark).(4)
For the watermarked image generated after linear difference expansion, the quadratic difference expansion is performed (the quadratic half watermark is embedded) and the pixel points with values 0 and 255 in the original image removed before embedding are add; finally, the watermarked image is generated.Figure 1
Flow chart of watermark embedding.


## 4. Watermark Extraction

The watermark extraction first uses the inverse quadratic difference expansion algorithm to extract the second half of the watermark information and restore the watermarked image with the embedding watermark using linear difference expansion. Then, the first half of the watermark is extracted by the inverse linear difference expansion algorithm and the original image is restored:(1)
Assuming that any pixel pair (x′, y′) in the watermarked image generated by linear difference expansion embeds the watermark information by quadratic difference expansion and the embedded watermark is b′. The value of the newly generated pixel pair (x″y″) is(16)x″=x′+y′2+x′−y′/2+b′+12,y″=x′+y′2−x′−y′/2+b′2.Supposex′ = 205, y′ = 200, and b′ = 1, then x″ = 204 and y″ = 201.Inverse transform is as follows:(17)l′=x″+y″2=2052=202,h′=x″−y″=3,h=2×x″−y″=2×3=6,x′=x″+y″2+h+12=202+3=205,y′=x″+y″2−h2=202−3=199.After the inverse transform, theh′ value is 3, which is an odd number, so the extracted watermark is 1.Since the two valuesx″ and y″ are odd and even, the values obtained are 205 and 199 by the foregoing inverse quadratic difference expansion algorithm.Therefore, we make the adjustment of the pixel pair generated by the quadratic inverse difference expansion. When two valuesx″ and y″ are odd and even and the extracted watermark is 1, the restored x′ remains invariant and y′ is plus 1; when two values x″ and y″ are odd and even and the extracted watermark is 0, the restored x′ and y′ remain unchanged; when x″ and y″ values are both odd or even and the extracted watermark is 1, the restored x′ is minus 1 and y′ remains unchanged; when x″ and y″ values are both odd or even and the extracted watermark is 0, the recovered x′ and y′ remain unchanged. An inverse difference expansion is performed using the newly generated pixel pair (x′, y′) to further extract the embedding watermark information.(2)
Furthermore, extract the watermark information and restore the original image using the linear inverse difference expansion for the image recovered by the quadratic inverse difference expansion.Assume that the watermark information is embedded by linear difference expansion for any pixel pair (x, y) in the original image. If the embedded watermark information is 1, the newly generated pixel pair (x′, y′) values are(18)x′=x+y22x−y+1+12=x+y2+x−y+1,y′=x+y2−2x−y+12=x+y2−x+y.Therefore,x′ − y′ = 2x − 2y + 1.Therefore, when the embedded one-bit watermark information is 1 in any pixel pair, the obtained new pixel pair difference is an odd value. Similarly, if the embedded watermark information is 0, the obtained new pixel pair difference is an even value. By this method, when we restore the original carrier image, if the difference of the pixel pair (a, b) in the watermarked image is odd, the embedded watermark information is 1; otherwise, it is 0. By this method, the watermark information embedded by linear difference expansion can be extracted.Watermark extraction is the inverse process of watermark embedding. The specific operation flow is as follows:(1)
Remove the pixel points with grayscale values 0 and 255 of the corresponding position in the watermarked image according to the received zero watermark(2)
According to the pixel points order in the watermarked image, from left to right and from top to bottom, two pixel points are taken out (the number of the selected pixel pair and half of the watermark are equal) to perform quadratic inverse difference expansion and extract the quadratic embedding watermark information(3)
After the quadratic inverse difference expansion, the newly generated pixel pair is adjusted(4)
Perform linear inverse difference expansion on the adjusted pixel pair to recover the original pixel pairs, and extract the linear embedding watermark information(5)
Perform inverse Arnold transform on the acquired watermark information, and finally generate the required watermark information(6)
The pixel pairs restored are combined in order, and the removed pixel values 0 and 255 are added to restore the original image


## 5. Experimental Results and Analysis

The standard images of size 512 × 512 such asLena and girl are used as original test images, as shown in Figure 2. The watermark is a binary image of size 32 × 32, as shown in Figure 3.Figure 2
Original images. (a)Lena. (b) Baboon. (c) Barbara. (d) Peppers.
(a)
(b)
(c)
(d)Figure 3
Watermark image.The reversible image watermarking algorithm generally requires that the carrier image can be completely recovered after the watermark is extracted. Therefore, the NC (normalized correlation) of the original carrier image and the carrier image recovered after the watermark is extracted can be used.Table1 denotes the integrity of the results of the 4 different types of watermarked images without any attack based on this algorithm. It shows that the original image can be recovered completely without any attack. This indicates that the algorithm is reversible.Table 1
Integrity assessment form without attack.
Images (512× 512)
Lena
Baboon
Barbara
Peppers
NC
1
1
1
1The watermarked images are compared with PSNR and SSIM using this algorithm and the algorithm in the literature [10], as shown in Table 2 (the data are taken as the average of 20 tests). The image shown in Figure 3 is used as embedded watermark information in this algorithm and the algorithm in the literature [10].Table 2
Comparison of PSNR (dB) and SSIM.
Image name
Proposed algorithm
Literature [10] algorithm
PSNR
SSIM
PSNR
SSIM
Lena
79.59
0.997
45.72
0.983
Baboon
76.87
0.995
47.37
0.985
Barbara
78.46
0.996
44.94
0.982
Peppers
77.76
0.996
45.81
0.981Compared with the algorithm in the literature [10], the highest PSNR of the above 4 original carrier images in this algorithm can be as 79.59 dB. This shows this algorithm has better invisibility. At the same time, the SSIM is also higher than the algorithm in the literature [10]. From Table 2, it is easy to note that the proposed algorithm outperforms the algorithm in the literature [10] in terms of the same payload capacity with good SSIM and PSNR values. The results presented here demonstrated that the proposed algorithm significantly increases the quality of watermarked images. Specific effects of visual and extraction are shown in Table 3.Table 3
Algorithmic experimental visual effect.
Image name
Original image
Watermarked image
Original watermark
Extracted watermark
PSNR
Lena
79.59
Baboon
76.87
Barbara
78.46
Peppers
77.76From Figures1–3, it is found that our eyes cannot feel the presence of watermark information in the watermarked images. The watermarked images have better visual effect, and the corresponding PSNR values indicate that they have better imperceptibility to different types of image algorithms, and the average PSNR value is as high as 78.17 dB.ThePSNR is utilized in estimating the deformation between the original cover image and resulted watermarked image when embedding 10, 30, 70, 90, and 100% from the allowed cover image capacity. From Table 4, it is easy to note that the proposed quadratic difference expansion-based reversible watermarking technique outperforms the literature [10] and literature [11] techniques in terms of payload capacity with good SSIM and PSNR values. The results presented here demonstrate that the proposed quadratic difference expansion-based reversible watermarking technique significantly increases the payload capacity while still keeping the visual quality of watermarked images.Table 4
Comparison between this algorithm, the method in the literature [10], and the method in the literature [11] in terms of payload capacity, SSIM, and PSNR for original images.
Image
Method
Payload in bytes
SSIM
PSNR (%)
10
30
70
90
100
Lena
Literature [10]
9767
0.918
45.78
43.48
41.58
39.78
38.64
Literature [11]
37992
0.9232
59.58
55.81
53.28
51.24
50.72
This algorithm
262144
0.993
74.11
71.97
69.12
67.24
65.47
Baboon
Literature [10]
11056
0.904
45.86
43.84
41.95
40.56
39.76
Literature [11]
14893
0.9085
58.77
55.24
53.35
52.28
51.34
This algorithm
262066
0.992
72.03
70.14
68.56
66.07
64.21
Barbara
Literature [10]
13232
0.893
45.66
42.89
39.54
37.10
36.65
Literature [11]
31423
0.9011
59.62
57.08
53.76
51.87
51.32
This algorithm
262144
0.992
73.39
70.87
68.16
66.50
64.98
Peppers
Literature [10]
8562
0.936
46.24
44.77
41.82
39.54
38.26
Literature [11]
29372
0.9393
58.89
55.43
51.85
50.94
50.07
This algorithm
262096
0.992
72.67
70.12
68.01
65.91
64.35When embedding more watermark information, the watermark embedding may be performed in a round of quadratic difference expansion to embed more watermark information, so two or more rounds of watermark embedding may be performed to complete the embedding.In order to estimate the visual quality of the watermarked image, this paper analyzes the performance of the algorithm by performing multiple rounds of watermark embedding on the original image (multiple rounds of watermark shown in Figure3).As can be seen from Table5, the watermarked images with high visual quality can be obtained by embedding watermark as shown in Figure 3 once. When embedding watermark as shown in Figure 3 twice and three times, the visual quality is still high. Compared with embedding watermark information once, the visual quality is not significantly reduced and the watermark information can be repeatedly embedded. On the premise of guaranteeing certain visual quality, more watermark information can be embedded.Table 5
Performance comparison of multiround watermarking embedding algorithms.
Image name
Evaluating indicator
One round
Two rounds
Three rounds
PSNR
SSIM
PSNR
SSIM
PSNR
SSIM
Lena
79.59
0.997
77.23
0.996
75.11
0.994
Baboon
76.87
0.995
74.92
0.994
73.03
0.993
Barbara
78.46
0.996
76.51
0.995
74.39
0.994
Peppers
77.76
0.996
75.63
0.995
73.67
0.994In order to further estimate the visual quality of the watermarked image, this paper analyzes the performance of the proposed algorithm by performing multiple rounds of watermark embedding on the original image (embedded watermark with maximum watermark embedding amount per round).In Table5, only part of the original image is selected according to the size of the watermark capacity to embed the watermark information. The embedding capacity is not large enough. In order to further test the performance of the algorithm, the maximum capacity of the image that can be embedded at one time is used as the size of the watermark embedding capacity. As shown in Table 6, when embedding once, twice, and three times, respectively, it is found that the generated watermarked image can still achieve greater visual quality and good SSIM. Moreover, the PSNR and SSI decrease little with the increase of embedding times. At the same time, after three times of maximum capacity embedding, the embedding rate approximates as high as 3 and the visual quality reaches 50.56, which shows that the overall performance of the algorithm is high, the invisibility is good, and the embedding capacity is large. On the premise of guaranteeing a certain visual quality, the watermarking information can be embedded repeatedly by using this algorithm, and the embedding capacity is very large.Table 6
Performance comparison of multiround watermarking embedding algorithms.
Image name
Evaluating indicator
One round
Two rounds
Three rounds
PSNR
SSIM
PSNR
SSIM
PSNR
SSIM
Lena
65.47
0.992
58.41
0.989
50.56
0.985
Baboon
64.21
0.991
57.19
0.987
49.07
0.982
Barbara
64.98
0.992
57.86
0.988
50.11
0.984
Peppers
64.35
0.991
57.27
0.988
49.31
0.983


## 6. Conclusion

In this paper, a reversible image watermarking algorithm based on quadratic difference expansion is proposed, which can effectively improve watermark embedding capacity and visual quality. After extracting the embedding watermark, the algorithm can losslessly recover the original carrier image. The watermark is embedded by quadratic difference expansion in this paper. The quadratic difference expansion algorithm is equivalent to the backup process of the traditional difference expansion algorithm. This algorithm is equivalent to perform another difference expansion based on the traditional difference expansion algorithm. The algorithm is equivalent to the repeating difference expansion watermarking algorithm twice, but the second difference expansion is equivalent to a callback process of the first difference expansion algorithm. So this algorithm effectively improves the embedding capacity and visual quality. The embedding capacity is doubled and the visual quality is improved significantly. The proposed reversible image watermarking algorithm mainly contributes to improving the watermark embedding rate while maintaining better visual quality than other algorithms.



---

*Source: 1806024-2020-01-09.xml*