Arab J Sci Eng DOI 10.1007/s13369-017-2898-z
RESEARCH ARTICLE - COMPUTER ENGINEERING AND COMPUTER SCIENCE
Robust Reversible Watermarking Algorithm Based on RIWT and Compressed Sensing Zhengwei Zhang1,2 · Lifa Wu2 · Shangbing Gao1 · He Sun2 · Yunyang Yan1
Received: 21 December 2016 / Accepted: 4 October 2017 © King Fahd University of Petroleum & Minerals 2017
Abstract In order to improve the robustness of existing reversible watermarking algorithms and strengthen the imperceptibility of watermarked images, a robust reversible watermarking algorithm based on redundant integer wavelet transform and compressed sensing is proposed. Firstly, the algorithm selects the high capacity embedding regions in the original image and then redundant integer wavelet transform is conducted within the selected areas, and wavelet coefficients matrices are obtained after the sparse. After that, the two intermediate-frequency parts of each wavelet coefficient matrix are conducted by compressed sensing with the same observation matrix, and the two generated compressed observation values are merged. Finally, the watermark is embedded into the observation value of intermediate-frequency coefficient part, to recover the sparse signal by using the reconstruction algorithm, and then the watermarked image is obtained through the redundant integer wavelet inverse transform. Simulation results indicate that the algorithm can not only realize blind extraction, but also significantly improve robustness, imperceptibility and embedded watermark capacity compared with other similar algorithms. It is easy to implement. What’s more, the generated watermarked images have high quality and can completely lossless restore the original carrier image without any attacks.
B
Zhengwei Zhang
[email protected]
1
Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai’an 223003, Jiangsu, People’s Republic of China
2
College of Command Information System, PLA University of Science and Technology, Nanjing 210007, Jiangsu, People’s Republic of China
Keywords Reversible watermarking · Redundant integer wavelet transform (RIWT) · Compressed sensing · Histogram adjustment · Arnold transform
1 Introduction Digital watermarking technology is widely used in the authenticity identification of digital documents, communication within a secret network, implied titles and notes, etc., and has become a research hotspot in the field of information security in recent years. Although distortion introduced by watermarking is usually small and is not easy to be perceived by the human perception system, any tiny distortion is not allowed in sensitive applications such as medical diagnosis images, satellite remote sensing images or legal evidence images. In order to solve this problem, people come up with the concept of reversible watermarking. This watermarking method can ensure that in the extraction end host media can be restored to the original state of non-embedded watermark accurately. Current research of reversible watermarking technology is mainly concentrated on the spatial domain, which is divided into three broad categories: the method based on image compression, the method based on the difference expansion and the method based on histogram shifting. In the literature [1], based on histogram shifting, Lee and Tsai presented a lossless data hiding technique. To maximize the payload capacity while keeping high visual quality, their technique divided the original cover images into blocks. Using a block size of 8×8, this technique had the maximum data hiding rate compared with other histogram shifting techniques. But the robustness of the algorithm was not taken into account by this method. Ruchira et al. [2] adopted the prediction of pixel gray value and neighborhood pixel value grounded on the coordination
123
Arab J Sci Eng
of logical operations. They embedded the watermark information into the prediction errors, thus reducing the image distortion degree. However, the algorithm needed pixel classification prediction, and calculation burden was too heavy. With arithmetic coding method, Mohammad et al. [3] used arithmetic coding to compress recovery information and then connected them with watermark information. Together, they were embedded into the original image. Compared with spatial domain algorithms, a wavelet transform is a good method to remove the correlation of data and improve the local compression ability. Then digital watermarking capacity can be improved. Meanwhile, if the watermark and carrier image are reversible, the signal must be reconstructed completely. In the calculation process, because floating-point numbers are used in traditional wavelet transform, it is impossible to achieve complete reconstruction of signal precisely [4]. The integer wavelet transform can make arithmetic process integral and ensure the accuracy of signal reconstruction [5]. It belongs to a reversible transform, and it is even simple and easy to be implemented. Tan et al. [6] applied the integer transform method to medical images and focused on solving the overflow problems of reversible hiding data in medical images, but the embedding capacity was low. Zhang et al. [7] proposed a blind digital watermarking algorithm of integer wavelet transform. The scrambled digital watermark was embedded into the cover image by means of modulo operation and modification of the integer wavelet transform coefficients of the cover image. The algorithm could not only realize blind extraction, but also significantly improve robustness, imperceptibility and embedded watermark capacity compared with other similar algorithms. However, the embedding capacity still needs further improvements. Because compressed sensing [8,9] has the properties of efficiently image compression and precisely image reconstruction, the combination of compressed sensing theory and digital watermarking technology can bring a reversible watermarking algorithm with high embedding capacity, strong anti-attack and good robustness. In order to improve the secrecy and robustness of image watermarking algorithms, Liu et al. [10] presented a digital image watermarking algorithm with double encryption on the basis of CS. According to the secrecy property of CS, the watermark and process of watermark embedding were both encrypted by CS and then orthogonal matching pursuit was used to reconstruct watermarked images. The proposed algorithm could withstand large-scale attacks on the premise of invisibility guaranteed, and it has better robustness and confidentiality. Di et al. [11] presented a novel scheme for high-capacity separable data hiding in an encrypted image based on compressive sensing. In the proposed method, CS was used for compression and encryption and the additional data were embedded onto CS measurements. The proposed method had the merits of high
123
capacity, anti-packet loss and cipher text compressibility, but it was complex and the embedding rate was not high. In this paper, after the advantages and disadvantages of the above algorithm are analyzed, a robust reversible watermarking algorithm is proposed based on the combination of a redundant integer wavelet transform and compressed sensing. In this algorithm, high-capacity reversible watermarking embedding technology can be obtained through the combination of redundant integer wavelet transform and compressed sensing. Histogram adjustment technology can control the data overflow, and two-way multiple Arnold transform scrambling watermark is used to improve the robustness of the algorithm. The process of watermark extraction and image restoration can be conducted as the inverse process of embedding. Also, it is simple and easy to be implemented. The structure of this paper is shown as follows: Sect. 2 introduces the basic methods and principles of the reversible watermarking algorithm. Section 3 presents the reversible watermarking embedding algorithm in detail. Section 4 describes the reversible watermarking extraction algorithm and the original image restoration algorithms, followed by the experiment results and performance analyses in Sect. 5. Last but not least, Sect. 6 concludes the algorithm of this paper and puts forward the future work.
2 Background Review 2.1 Watermark Image Scrambling Scrambling is to transform the position of a digital image or gray level, which makes image “beyond recognition,” so as to achieve the purpose of confusing the third party, and to a certain extent ensure secure information transfer. In addition, watermark image scrambling can effectively enhance the robustness against watermarked image shearing operations and the watermarking security. Arnold transform is one of the most commonly used image scrambling transform, and it is defined as follows:
x y
1 1 x = mod N 1 2 y x, y ∈ {0, 1, 2, . . ., N − 1}
(1)
(x, y) are original pixel coordinates, (x , y ) are the new coordinates of the original pixels after transform; N is the size of the image. An Arnold transform is completed after the transform of all pixels in the image. With an increase in the number of iterations, the image is chaotic, but when it is repeated a certain number of times, the image will be restored to the original image, and an Arnold transform cycle is completed. The traditional Arnold transform matrix is simple and can be easily decrypted by attackers when it suffers malware
Arab J Sci Eng
attacks. When the original image is restored, the confidentiality and robustness are not strong. In order to enhance the robustness and security against attacks of the digital image watermarking system, in this paper, the traditional Arnold scrambling transform can be improved, and the improved scrambling method is as follows:
x y
=
c d 1 1 2 1 x mod N 1 2 1 1 y x, y ∈ {0, 1, 2, . . ., N − 1}
(2)
where (x , y ) are the original pixel coordinates after transform, (x, y) are the original pixel coordinates; N is the size of the image; c, d are the times of scrambling. Equation (1) scrambles the image in one direction. Equation (2) chooses two directions at the same time to scramble an image and does multiple iterations in both directions. Arnold transform is one-to-one mapping, and each change of transform parameters c and d is randomly generated. Compared with the traditional Arnold transform, it is not easy to be decrypted, and it enhances the robustness and security against attacks of the whole digital image watermarking system. 2.2 Redundant Lifting Integer Wavelet Transform 2.2.1 Redundant Discrete Wavelet Transform The redundancy discrete wavelet transform (RDWT) can be treated as a kind of approximation of continuous wavelet transform [12,13], and it is a non-orthogonal wavelet transform. Compared with discrete wavelet transform, the redundancy wavelet transform has a larger embedding capacity and stronger robustness. The redundancy discrete wavelet decomposition is conducted on an image and shown in Fig. 1, and a onedimensional RDWT is performed on the line of the image, where g and h represent a high-pass filter and low-pass filter, respectively; the row will then transform the resulting high-pass and low-pass redundant super coefficients, respectively, as a new image; the column is transformed for the one-dimensional RDWT; Finally, with four RDWT coefficients of the image: low-frequency coefficient image A, diagonal, horizontal and vertical directions of the three highfrequency coefficients of image for D, H and V , this can continue to repeat the previous low-frequency coefficients of image wavelet transform steps until a satisfactory decomposition scale is obtained. Because the RDWT maintains a constant sampling rate at all levels of decomposition, it has the features of translationinvariant space. What’s more, the signal is in the redundant wavelet transform and will not conduct a sampling process itself, but is inserted between every two filter coefficients
Fig. 1 Redundant discrete wavelet decomposition of the image
LL2
LH2
HL2
HH2
HL1
LH1
HH1
LL2
HL2
LH2
HH2
LH1
HL1
HH1
Fig. 2 Comparison of two level of RDWT and DWT decomposition
of zero value to realize filtering extension. Meanwhile, the RDWT has the time-shift invariance property and introduces the redundant spread spectrum watermark, so that the spread spectrum technology can improve the robustness of the watermarking algorithm, which makes its robustness better than the DWT (as shown in Fig. 2), so we adopt the RDWT method for watermark embedding. 2.3 Integer Wavelet Transform The integer wavelet transform (IWT) can be summed up as a special way of discrete wavelet transform (DWT) [14]. With the reversible watermarking technology, the receiver is asked to recover the original image from the watermarked image completely, which requires that information cannot be lost in wavelet transform or inverse transform, because the generation coefficient is a floating-point number after DWT, which often cannot accurately reconstruct the original signal. The lifting method to construct the tight branch collection of biorthogonal wavelets can be used for each filter after the data derive from integer-to-integer wavelet transform, and this kind of transformation is completely reversible and reconstructed. The IWT is mainly in the airspace of the signal, and the signal is a series of operations in order to realize the signal decomposition frequency, and the process is mainly divided into: Split, Predict and Update. Split: the original information is split into two nonoverlapping subsets (the number sequences of even even j−1 and odd odd j−1 ), denoted as Eq. (3):
123
Arab J Sci Eng
Split(s j ) = (even j−1 , odd j−1 )
(3)
prediction operator P and make odd j−1 = Predict: use P even j−1 . The detailed information is confirmed and odd j−1 is replaced according to the difference. Expressions are shown in Eq. (4): d j−1 = odd j−1 − P(even j−1 )
(4)
where d j−1 is the high-frequency detailed signals of the next level obtained in the process of prediction, means round down. Update: by updating the operator U , the new subset s j−1 takes the place of even j−1 . Expressions are shown in Eq. (5): s j−1 = even j−1 + U (d j−1 )
(5)
where s j−1 is used as the low-frequency detailed signal of the next level. Through the above three steps, the original signal s j is decomposed into high-frequency signal d j−1 and lowfrequency signal s j−1 , and the multi-resolution decomposition of the signal is completed. At the same time, the IWT has an advantage that as long as a wavelet is positively transformed, the inverse transform can be obtained by the inverse transform. Transform process is simple and easy to be implemented, and its expression is shown in Eqs. (6–8): even j−1 = s j−1 − U (d j−1 ) odd j−1 = d j−1 − P(even j−1 ) s j = Merge(even j−1 , odd j−1 )
(6) (7) (8)
Merge() in Eq. (8) means that even j−1 and odd j−1 are combined, thus completing the reconstruction of the signal. The redundant ascension integer discrete wavelet transform (RIWT) is a combination of RDWT and IWT, which absorbs the advantages of both algorithms and can embed high-capacity watermark. The algorithm is characterized by higher robustness and stronger invisibility, and it can achieve perfect reconstruction of original image. 2.4 Compressive Sensing Candés [15] and Donoho [16] came up with the concept of compressed sensing in 2006 formally on the basis of related research, and this theory breaks through the bottleneck of the classic Shannon theorem. Its core idea is to combine compression with sampling. As a new sampling theory, compressed sensing acquires the non-adaptive linear projection of the signal (measured value) by exploiting the sparse feature of the signal under the condition of far less than Nyquist sampling rate. Then,
123
according to the reconstruction algorithm, the original signal is reconstructed by the measurement value. Compressed sensing measurement as the content of image features can describe characterization of the image. The data quantity after it handled is far less than the storage of original image. In addition, the measurement matrix is the encryption function which ensures the attacker in the case of not knowing the key to restore the original image by measuring the value of the content, satisfying the requirements of the watermarking confidentiality. Compared with other self-embedding watermarking algorithms, the information extraction of the original image based on the compressed sensing watermarking is more comprehensive and has better security. However, generally speaking, a sparse natural signal is not absolute. Sparse representation is necessary in some sparse groups. Considering a real value one-dimensional discrete signal x ∈ R N , it can be expressed in a set of orthogonal basis Ψ ∈ R N ×N as follows: x = Ψs
(9)
where s ∈ R N is the orthogonal transformation coefficient vector. Obviously x and s are equivalents of the same signal. x is the time-domain representation of the signal, and s is the Ψ domain representation of the signal. When the signal x on the orthogonal basis Ψ only has K N nonzero coefficient (or greater than zero coefficient), known Ψ as the signal sparse matrix x, signal x in Ψ is K -sparse, Eq. (9) at this time is the sparse representation of x. If x is K -sparse, according to the compressed sensing theory, in the case of not transforming directly through an M × N (M N ) matrix Φ is not associated with Ψ for observed value of signal x is y ∈ R M : y = Φx = ΦΨ s = Θs
(10)
where Θ = ΦΨ . We call M × N matrix Φ as observation matrix and N × N matrix Ψ as the sparse decomposition matrix. Compress sensing matrix Θ = ΦΨ is an M × N matrix. Since the dimension M of the observed value y is far less than the dimension N of signal x, the purpose of compression is achieved. When matrix Θ meets the isometric rule of the limited nature, the compressed sensing theory can get sparse coefficients by solving the inverse problem of Eq. (10). And x is obtained by Eq. (9). Candés et al. prove that the compressed sensing signal reconstruction problem can be solved by getting l0 -norm minimum estimated value x in Eq. (10), mathematical models for: Sˆ = arg min s0 s.t. y = Θs
(11)
Arab J Sci Eng
But for l0 -norm solution is a NP problem, it is difficult or impossible to solve or verify the reliability of the solution, so it is necessary to seek a more effective equivalent method. Minimum l1 -norm problem under certain conditions is equivalent to l0 -norm minimization problem in that they can get the same solution. Therefore, Eq. (11) can be converted into the problem of l1 -norm optimization. Sˆ = arg min s1 s.t. y = Θs
(12)
Namely Eq. (12) is a convex optimization problem and can be changed into the linear programming problem. 2.5 Data Overflow Solutions Though watermark information is embedded into coefficients after wavelet transform in images can guarantee the watermark capacity, it creates new problems. The phenomenon of “overflow” [17] may happen after embedding watermark data on redundant integer wavelet inverse transform. That is to say, the calculated value is beyond the range of 0–255. In order to solve this phenomenon, histogram shrinkage is used to adjust the histogram. In this way, overflow does not occur or occurs very rarely. Usually, overflow occurs only on the gray value between 0 and 255 pixels. In order to ensure the translation operations of carrier images, pixels will not overflow, and the original image I is scanned with an “inverted S-order.” The one-dimensional sequence {I (i)|1 ≤ i ≤ size, i ∈ Z } is expanded, and Eq. (13) can be obtained by the histogram of the m layer: ⎧ ⎨ I (i) + m, I = I (i) − m, ⎩ I (i) ,
I (i) ∈ [m, 2m − 1] I (i) ∈ [255 − 2m + 1, 255 − m] others (13)
Contraction pixel location is marked with an adjustment record (the Location map) whose size is just like the original image, and the method is as Eq. (14). The generated Location map is conducted by lossless compression through using run-length encoding, which is used to recover the original carrier image in the watermark embedding and extraction processes. Location map =
1, 0,
Pixel shrinkage change Pixel not changed
(14)
3 Watermark Embedding Algorithm The reversible image watermarking algorithm is different from the conventional watermarking algorithm. The watermark is embedded by lowering the original image coding
redundancy or redundancy between pixels. Obviously, effective embedded watermark capacity and the original image redundancy are highly correlated. In the smooth area, due to the large data redundancy, the watermark embedding capability is strong. On the contrary, in texture area, due to smaller data redundancy, the watermark embedding capacity is weak. Therefore, this paper first blocks and calculates texture complexity of each piece of the original image and then selects low texture complexity, which is relatively smooth piece of domain for watermark embedding. Concrete steps of embedding are as follows: Step 1 The watermark image W is scrambled and dealt with by using the improved Arnold transform, and the generated transform parameters c and d are recorded randomly. In addition, it is marked W after scrambling watermark; Step 2 The carrier image I is divided into n sub-blocks X i , i ∈ {1, 2 . . . n} of the same size and non-overlapping. Through calculating entropy value of each block, an entropy threshold T1 (the entropy value T1 is mainly concerned about the amount of embedded watermark information) is set, put all the collected blocks and divide them into two categories: smooth area I1 and texture area I2 ; Entropy of the image gray level co-occurrence matrix [18] S is defined: S=−
255 255
P(i, j)logP(i, j)
(15)
i=0 j=0
where P(i, j) is the value at the point (i, j) of the gray level co-occurrence matrix P; Step 3 Use raster scan, and all smooth blocks of the carrier image I are extracted by scanning each sub-block from left to right and from top to bottom, forming a group for a smooth zone I1 collection. All block indexes of collection I1 are recorded and transmitted to the receiver; Step 4 Histogram adjustment is conducted on the contraction area of smooth zone I1 to prevent results from overflowing after the last embedding data. Use Eq. (14) and all I1 collection areas are adjusted by histogram. Accordingly, I1 collection is obtained and the Location map is recorded; Step 5 First-level RIWT is conducted on each piece L of I1 collection after adjustment, get L HL1 and L LH1 intermediate-frequency coefficient matrices and the wavelet coefficients are sparse. I2 collection makes no changes; Step 6 Random projection is performed by adopting structured stochastic matrix and treated as observation matrix Φ, compressed image information is obtained, namely the measured values L Y 1 and L Y 2 of Eq. (10).
123
Arab J Sci Eng Original image I
Watermark image W
Block and calculate the entropy
Smooth area I1
Texture area I2
Histogram adjustment
Arnold scrambling
RIWT on each block of I1 '
LHL 1 and LLH 1
Adjustment record
Measurements LY1 and LY2 are obtained by CS random projection
LHH 1 and LLL 1
Watermark embedding Combine into Sparse matrixQ
Recover L'HL 1 and L'LH 1
Inverse RIWT Watermarked image IW1
Merge Watermarked image IW
Fig. 3 Watermark embedding process
The measured values L Y 1 in series with L Y 2 make vector matrix L Y . Make L Y 1 on behalf of the observed value of even number sequence in vector matrix L Y , L Y 2 is adjacent previous observed value of odd number sequence matched with the corresponding even number sequence observed values. L Y 1 and L Y 2 are called a sequence pair. During watermark embedding process, the only change L Y 1 , through the sequence pair < L Y 1 , L Y 2 >, the watermark information is embedded by the parity quantization; Step 7 Combine W in Step 1 with Location map in Step 4 to generate new watermark information W , and through the parity quantization embed watermark information to L Y 1 that from Step 6. can be hidden When αL Y 1 /L Y 2 is even, L Y 1
⎧
LY 1 ⎨ L + 1 Wi = 1 Y2
L Y 2 = LY 1 ⎩ L Wi = 0 Y2 L
(16)
where is the floor function, Wi represents the watermark information, α represents the embedded adjustment coefficient; Step 8 After the watermark is embedded, the compressed sensing recovery algorithm is adopted to get the observation values L Y 1 and L Y 2 of the two intermediatefrequency parts in each block operation of the embedded watermark, and the observation matrix Φ is used for recovery, the intermediate-frequency coefficient matrices L HL1 and L LH1 of the restoration are obtained; Step 9 The sparse coefficient matrix Q is obtained by combining the rest two parts of each coefficient matrix. Inverse RIWT is conducted on block Q of all regions I1 , and then the I2 area is merged to obtain the watermarked image Iw . The watermark embedding process proposed in this paper is shown in Fig. 3.
Y2
When αL Y 1 /L Y 2 is odd, L Y 1
⎧
LY 1 ⎨ L Wi = 1 Y2 L
Y 2 = L Y1 ⎩ L +1 Wi = 0 Y2 L Y2
123
4 Watermark Extraction and Carrier Recovery Algorithm (17)
The process for the watermark extraction and carrier recovery algorithm is shown in Fig. 4.
Arab J Sci Eng
Fig. 4 Watermark extraction process with the carrier recovery algorithm
The detailed steps of the watermark extraction and carrier recovery algorithm are as follows: Step 1 The watermarked image Iw is divided into n small non-overlapping pieces of the same size, and the smooth blocks are extracted according to the received block index number. Using the way of raster scan, the smooth zone I1 collection consists of extracted smoothing blocks according to scanning from left to right and from top to bottom; Step 2 The smooth regions are conducted by RIWT. Each sub-block transformation generates two intermediatefrequency coefficient matrices L HL1 and L LH1 . The same measurement matrix Φ projection is used, and two measurement values L Y 1 and L Y 2 are obtained. L Y 1 and L Y 2
series constitute the vector matrix L Y . L Y 1 represents the observed values of even numbers in the observed L Y ; L Y 2 is an adjacent previously odd sequence observed values to match the corresponding even sequence observed values. Here, L Y 1 and L Y 2 are called a sequence pair. Step 3 In turn, the watermark information is detected and , L
extracted from each observation sequence L Y1 Y2 of each observation value. If αL Y 1 /L Y 2 is close to even, information extracted will be the watermark 0. If αL Y 1 /L Y 2 is close to odd, the watermark information extracted will be 1. On this account, the watermark information is extracted from each sequence; thus, the watermark information of the whole image is obtained.
123
Arab J Sci Eng
Lena
Baboon
Barbara
Peppers
Fig. 5 Original image
Step 4 As per Step 3, w consists of two parts: scrambling watermark w and histogram adjustment record Location map. Inverse Arnold scrambling transform is conducted on the extracted w to get the original watermark. Step 5 For the measured values L Y 3 and L Y 4 of two new intermediate-frequency coefficients after extracting the watermark; the observation matrix Φ is used for restoration, and the intermediate-frequency coefficient matrix of restoration is obtained. Step 6 The sparse coefficient matrix Q is obtained by combining the rest two coefficient matrixes of each block, and inverse RIWT is conducted on block Q of all regions I1 . Step 7 With the extracted adjustment records of Step 4, the partitioned histogram is restored on I1 area, and the recovered original carrier image is obtained after merging I1 and I2 .
5 Experimental Results and Performance Analysis In this paper, all experiments are conducted based on Windows 7 operating system and MatlabR2011a experiment platform. The original carrier images with size of 512 × 512 Lena, Baboon, Barbara and Peppers gray images are shown in Fig. 5. The 64 × 64 sized binary image used for watermark is shown in Fig. 6. In view of research targets of the reversible watermarking algorithm, this paper mainly uses the embedding capacity, the visual quality of the watermarked image, the integrity assessment, the evaluation of watermark robustness, the structural similarity and so on to evaluate reversible watermarking.
Watermark Image 1 Fig. 6 Watermark image
quality the watermarked image has. The smaller the PSNR is, the more the representative image distortion is, and the more serious visual quality loss the watermarked image suffers from. The calculation formula of the PSNR is displayed in Eq. (18): PSNR = 10log
123
2552
1 MN
M−1 N −1 i=0
j=0
[I (i, j) − I (i, j)]2 (18)
I (i, j) , I (i, j), respectively, denote the pixel value at (i, j) of the original image and the watermarked image. M, N , respectively, represent the rows and columns of the image. It is generally believed if the lost image quality is partial and the PSNR value on the visual quality of reconstruction is no less than 30 dB, and its visual quality is still acceptable. 5.2 Structural Similarity Although the PSNR has been widely used in watermarked image quality assessment, its mathematical definition has some limitations, and the pixel correlation and human visual system characteristics are not taken into account. Under this background, a method of image quality assessment, which is based on the similarity of image structure, was proposed by Wang [19], and it was widely used. The structural similarity (SSIM) has been used to evaluate the quality of the watermarked images. It is defined as (19):
5.1 Visual Quality Assessment Currently, the peak signal-to-noise ratio (PSNR) is one of the main indicators to evaluate the visual quality of reversible watermarking. The greater the PSNR value is, the less the representative image distortion is, and the better the visual
Watermark Image 2
SSIM(x, y |w ) =
(2w¯ x w¯ y + C1 )(2 σwx w y +C2 ) (19) 2 + σ2 +C ) ¯ (Wx2 + W¯ y2 + C1 )(σw 2 wy x
where C1 , C2 are small constants, w¯ x is the mean value of the region wx , and w¯ y is the mean value of the region w y . σw2 x
Arab J Sci Eng
is the variance of wx , and σwx w y is the covariance between the two regions. A higher value of the SSIM implies a higher quality level of watermarked image. The value range of SSIM is [0, 1]. SSIM = 0 indicates that the corresponding two images are completely different. SSIM = 1 indicates that the corresponding two images are exactly the same. In the evaluation of the reversible information hiding algorithm, the SSIM value of the hidden image is close to 1 as much as possible. 5.3 Embedding Capacity Assessment The reversible watermarking has a valid embedding capacity. That is to say, an important evaluation indicator of embedding capacity is that the number of bits can be embedded into per pixel. The embedding quantity can be divided into actual embedded quantity and effective embedded quantity. The actual embedding quantity is the number of bits embedded in the information hiding method by itself. The effective embedded quantity expresses that the actual embedded quantity subtracts additional information (in order to restore images to be transmitted to the receiver or with secret information embedded into the image information). Commonly, the effective embedding quantity index is used as embedding rate ER and expressed as: ER =
Numsec − Numextra Numpixel
(20)
In Eq. (20), Numsec denotes the number of bits in the secret embedded information; Numextra denotes the number of bits in the additional information; Numpixel denotes the number of pixels in the image carrier. The embedding rate can be more intuitionistic to reflect the embedding capacity of a scheme. 5.4 Integrity Assessment Generally, the reversible watermarking algorithm requires carrier images to completely recover after extracting watermark. Therefore, it is measured by the normalized correlation (NC) of the original carrier image and the carrier image of recovery after watermark is extracted. The calculation formula is shown in Eq. (21): M−1 N −1 NC1 =
i=0 j=0 I (i, M−1 N −1 i=0 j=0 [I
j) I (i, j) (i, j)]2
(21)
where I (i, j), I (i, j), respectively, denote the pixel value at (i, j) of the original image and the carrier image of recovery after the watermark is extracted. M and N denote, respectively, the rows and columns of the image. For the original carrier image and restoring the carrier image, the NC1 is
required to be 1, which means the carrier images are generally completely recovered. 5.5 The Watermark Robustness Evaluation The watermarked images will be inevitably disturbed by the noise, and then the quality and accuracy of watermark extraction will be affected in the process of transmission. This requires digital watermarking to have a certain ability to resist noise. In the experiment, normalized correlation (NC) is used as a measure of watermark robustness. Define w(i, j), w (i, j) as the pixel values at (i, j) of the original watermark image and the extraction watermark image, respectively. M and N are denoted as the rows and columns of the image, respectively. Its computation formula is shown in Eq. (22): M−1 N −1 NC2 =
i=0 j=0 w (i, j) w (i, M−1 N −1 2 i=0 j=0 [w (i, j)]
j)
(22)
NC2 is used to describe the quality of the extracted watermark. If the NC2 value is closer to 1, the watermarking algorithm will have stronger robustness. When NC2 < 0.5, it is thought this extraction algorithm fails and almost couldn’t extract the watermark information. 5.6 The Analysis of Experimental Performance Results In this paper, regional division is conducted on the image texture through entropy S. If the threshold value 1 T1 of entropy value is different, the setting of smooth zone I1 will not be the same. Therefore, the threshold value 1 T1 of entropy value is different, the watermark embedding capacity of carrier image, NC2 , PSNR is also different. Therefore, in this paper, in order to achieve a larger embedding capacity and better NC2 , PSNR, given threshold value 1 T1 , the number of block I1 is 2 times that of block I2 . What’s more, in this paper the T1 value is set. Through a large number of experiment verifications, we obtain better visual quality, and set the watermark embedding strength factor α = 10. In this paper, the following results are calculated with the above parameter values. The algorithms in this paper and in the literature [20,21] based on the original carrier image after using 4 × 4 blocks, the PSNR and SSIM are shown in Table 1 (the average of data taken 20 tests). Compared with the algorithm in the literature [20] and the literature [21], the highest PSNR of the above 4 original carrier images in this algorithm can be as 42.56 dB and has better invisibility. At the same time, the SSIM is also higher than the algorithms in the literature [20] and the literature [21]. In Table 1, it can be easily noted that the proposed algorithm outperforms the algorithms in the literature [20]
123
Arab J Sci Eng Table 1 Comparison of PSNR (dB) and SSIM
Table 2 Algorithm experiments visual effects
Image name
Proposed algorithm
Literature [20] algorithm
Literature [21] algorithm
PSNR
SSIM
PSNR
SSIM
PSNR
SSIM
Lena
42.56
0.9362
34.63
0.9188
40.25
0.9254
Baboon
41.49
0.9232
36.86
0.9047
39.92
0.9185
Barbara
41.11
0.9425
34.94
0.9212
40.01
0.9411
Peppers
40.62
0.9569
34.90
0.9345
39.53
0.9427
Image name
Original image
Original
Extracted
PSNR/
watermark
watermark
dB
Lena
42.56
Baboon
41.49
Barbara
41.11
Peppers
40.62
and the literature [21] 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 2. As observed from the figures, it can be found that human eyes do not feel the existence of watermark information in watermarked images. The corresponding PSNR value shows that images have better imperceptibility by using different types of algorithm. When the visual effect of the watermarked image is good, the average PSNR value can be as high as 41.45 dB. From Tables 1 and 2, it can be seen that this algo-
123
Watermarked image
rithm has a good sense of different texture images and can meet the requirements of visual perception. In Table 3, the performance results can be obtained after using the algorithm in this paper, which is focused on four different types of watermarked images without any attacks, indicating that, when it is not attacked, the algorithm not only has a clear image visual effect and good robustness, but can also restore the original carrier image completely and realize the image reversibility. In Table 4, the performance results can be obtained after the common geometric attacks (added white noise, Gaussian filtering, JPEG compression, rotation, enlarge, narrow)
Arab J Sci Eng Table 3 No attack of this algorithm and performance evaluation test table
Image (512 × 512) block (4 × 4)
Lena
Baboon
Barbara
Peppers
PSNR/dB
42.56
41.49
41.11
40.62
NC1
1
1
1
1
NC2
1
1
1
1
ER/bpp
0.015
0.015
0.015
0.015
Table 4 Attack algorithm and performance evaluation from experiments Original image attack type
Rotate 15 ◦ C 30 ◦ C
Lena
Baboon
Barbara
Peppers
PSNR/dB
NC2
PSNR/dB
NC2
PSNR/dB
NC2
PSNR/dB
NC2
38.47
0.9142
35.30
0.8762
36.38
0.8923
34.20
0.9144
41.03
0.9775
39.75
0.9684
39.63
0.9791
38.70
0.9671
Shrink 20%
39.49
0.9722
38.64
0.9598
37.76
0.9655
37.59
0.9723
Enlarge 20%
40.68
0.9726
39.37
0.9772
38.40
0.9741
38.23
0.9756
Gaussian filter (3 × 3, σ = 0.5)
36.57
0.9154
35.54
0.8579
34.56
0.8711
34.30
0.8993
Gaussian filter (3 × 3, σ = 0.3)
39.24
0.9958
38.88
0.9544
38.97
0.9762
38.77
0.9903
Add white noise (ρ = 0.01)
37.28
0.9835
36.08
0.9468
35.10
0.9576
35.05
0.9773
JPEG (Q = 60)
36.98
0.9241
36.70
0.9096
35.79
0.9187
35.54
0.9376
Rotate
Table 5 Performance comparison results against geometric attacks Performance attack type
PSNR/dB
SSIM
NC2
Proposed algorithm
Literature [22] algorithm
Proposed algorithm
Literature [22] algorithm
Proposed algorithm
Literature [22] algorithm
Direct extraction
42.56
34.63
0.9362
0.9173
1
1
Salt-and-pepper noise (ρ = 0.01)
38.29
31.15
0.9155
0.9088
0.9642
0.9274
Mean Filter (3 × 3)
39.06
32.39
0.9286
0.9116
0.9544
0.9610
JPEG (Q = 70)
37.86
33.42
0.9131
0.8927
0.9241
0.9712
are conducted on four different types of watermarked images using the algorithm in this paper. Its PSNR value of the watermarked image and the NC2 value of extraction watermark have been listed. Table 4 shows that this algorithm has good robustness against common geometric attacks. The results of Table 4 can be used to objectively evaluate the algorithm performance. This paper shows that the method can resist common attacks effectively. In particular, when Lena rotates 30◦ , the PSNR is 41.03 dB, and the watermark NC2 is 0.9775 under corresponding attacks. This algorithm not only has strong robustness, but can also accurately extract watermark. In addition, to verify the algorithm’s superiority against common geometric attacks, Lena image and the watermark of the same indicators are adopted in this paper and the literature [22], and then salt-and-pepper noise, average filtering, JPEG
compression and so on are added to the geometry simulation experiments, respectively. The comparison results are shown in Table 5. It can be seen from the experiment results in Table 5 that the PSNR values of the attacked watermarked images are obtained by the algorithm, which are higher than the corresponding values in the literature [22]. Apparently, our algorithm also has great robustness to general image processing operations and has much better performances than the method in the literature [22]. As per Table 5, it is easy to note that the proposed reversible watermarking technique outperforms the algorithm in the literature [22] with good SSIM and PSNR values under the same payload capacity. For different types of images, when the watermark embedding capacity is the same, the required entropy threshold T1 is not the same; for the same image, when the water-
123
Arab J Sci Eng Table 6 Comparison of embedding rate Image name
Proposed algorithm
Literature [11] algorithm
r = 30%
r = 50%
PSNR/dB
ER/bpp
r = 70%
PSNR/dB
ER/bpp
PSNR/dB
PSNR/dB
ER/bpp
ER/bpp
Lena
39.89
0.3
38.17
0.5
36.27
0.7
35.35
0.5
Baboon
39.31
0.3
38.51
0.5
36.31
0.7
34.06
0.5
Barbara
39.17
0.3
38.28
0.5
34.69
0.7
33.54
0.5
Peppers
38.78
0.3
37.15
0.5
34.55
0.7
34.27
0.5
Table 7 The proposed algorithm performance (PSNR:Db, ER: bpp) Image name
r = 30%
r = 50%
θ = 3/4 PSNR
θ = 1/2 ER
PSNR
r = 70%
θ = 3/4 ER
PSNR
θ = 1/2 ER
PSNR
θ = 3/4 ER
PSNR
θ = 1/2 ER
PSNR
ER
Lena
41.13
0.225
42.34
0.15
39.19
0.375
40.73
0.25
37.87
0.525
39.66
0.35
Baboon
40.39
0.225
41.28
0.15
39.12
0.375
40.12
0.25
37.25
0.525
39.68
0.35
Barbara
39.77
0.225
40.97
0.15
38.77
0.375
39.24
0.25
35.59
0.525
39.04
0.35
Peppers
39.68
0.225
40.23
0.15
38.01
0.375
39.19
0.25
35.82
0.525
38.51
0.35
Table 8 Results of 4 images in different amounts of embedded
Effective embedding capacity
Lena PSNR/dB
Baboon PSNR/dB
Barbara PSNR/dB
Peppers PSNR/dB
200 bit
52.48
52.15
51.50
50.28
300 bit
51.41
51.47
51.06
49.88
500 bit
50.32
49.68
50.05
49.13
1000 bit
47.56
47.19
46.11
46.64
2000 bit
44.02
43.77
43.25
42.85
5000 bit
41.36
40.57
39.89
40.22
mark embedding capacity is not the same, threshold T1 is not the same. In order to better describe the influence degree of embedding different quantities of watermark information into the same or different types of images, in this paper, with the ratio of r between the required smooth blocks and the total number of blocks represents the relationship between watermark embedding capacity and PSNR. The comparison of watermark embedded rates between the algorithm in this paper and in the literature [11] after the original carrier image with 4 × 4 blocks is shown in Table 6. Table 6 demonstrates that the maximum number of embedded watermark can reach 0.7bpp (r = 70%), and the maximum number of embedded watermark in the literature [11] is only 0.5bpp. The maximum capacity of embedded watermark of the algorithm is more than that in the literature [11], and when the largest embedding capacity of the carrier image is embedded, the watermarked image has better visual quality than in the literature [11]. The results presented here
123
demonstrate that the proposed reversible watermarking technique has vastly improved the payload capacity while still keeping the quality of watermarked images. For the observation matrix Φ of size M × N , if θ = M/N , the number of matrix measurement values obtained is not the same. For one piece of image, when the same number of smooth blocks are selected to embed watermark, if θ value is different, the maximum watermark embedding capacity would be different, corresponding to different PSNR of watermarked images, as shown in Table 7. The data hiding performance test of different embedding capacities is conducted on the gray image, whose size is 512× 512 Lena, Baboon, Barbara and Peppers. The 4 × 4 blocks are adopted in original carrier images, and the experiment data are shown in Table 8. Contrast with the algorithm in the literature [23], in order to keep similar embedding rate and the same sampling rate, we set the embedding capacity a = 200, 260, 320, 400, 500
Arab J Sci Eng Table 9 Comparisons of PSNR of Lena by keeping same embedding bits as proposed method in the literature [23] Effective embedding capacity
Proposed algorithm PSNR/dB
Literature [23] PSNR/dB
200 bit
52.48
39.15
260 bit
51.89
38.79
320 bit
51.02
37.88
400 bit
50.86
37.49
500 bit
50.32
36.71
800 bit
48.27
36.61
and 800. The simulation results are shown in Table 9. The proposed algorithm has better imperceptibility from the above simulation results. It can be seen from Table 8 that the smaller the watermark embedding capacity is, the better digital watermarking image quality will be generated correspondingly. In addition, Tables 6, 7 and 8 indicate that in order to obtain a larger watermark embedding rate and embed more watermark information, the visual quality of correspondingly watermarking images will severely decrease, and usually quality requirements for watermarking images are invisible, so it has little practical significance to pursue large quantity of watermark embedded merely.
6 Conclusion In this paper, a robust reversible watermarking algorithm is proposed, which is based on RIWT and compressed sensing. This algorithm has combined the technology of RIWT with inverse transform, compressed sensing projection and reconstruction, gray histogram adjustment, recovery and scrambling, non-scrambling and so on, which can improve the algorithm performance. The experiment results have shown that the algorithm can not only realize blind extraction, but also significantly improve robustness, imperceptibility and embedded watermark capacity compared with other similar algorithms. It is easy to be implemented. What’s more, the generated watermarked images have high quality and can completely lossless restore the original carrier image without any attacks. In order to perfect the reversible image watermarking algorithm, the further research directions have been confirmed: (1) a large capacity embedding of reversible digital image watermarking should be researched; (2) the RIWT is applied to the multilayer embedding algorithm of reversible watermarking; and (3) the reversible image watermarking is applied to real life and a perfect reversible watermarking system is established.
Acknowledgements This work is supported by the Jiangsu province Natural Science Foundation of China (No. BK20131069). At the same time, this work is also supported by the National Natural Science Foundation of China (NSFC) (No. 61402192).
References 1. Lee, C.-W.; Tsai, W.-H.: A lossless data hiding method by histogram shifting based on an adaptive block division scheme. In: Wang, P.S.P. (ed.) Pattern Recognition and Machine Vision, pp. 1– 14. River Publishers, Aalborg, Denmark (2010) 2. Naskar, R.; Chakraboty, R.S.: Reversible image watermarking through coordinate logic operation based prediction. Comput. Sci. 7093, 190–203 (2011) 3. Awrangjeb, M.; Kankanhalli, M.S.: Lossless watermarking considering the human visual system. Lect. Notes Comput. Sci. 2939, 329–336 (2004) 4. Muhammad, A.; Malik, S.A.; Khan, A.: Intelligent reversible watermarking in integer wavelet domain for medical images. J. Syst. Softw. 85, 883–894 (2012) 5. Verma, V.S.; Jha, R.K.: Improved watermarking technique based on significant difference of lifting wavelet coefficients. Signal Image Video Process. 9(6), 1443–1450 (2015) 6. Tan, C.K.; Ng, J.C.; Xu, X.T.; et al.: Security protection of DICOM medical images using dual-layer reversible watermarking with tamper detection capability. J. Digit. Imaging 24(3), 528–540 (2011) 7. Zhang, D.H.; Wang, Y.P.; Zhang, J.W.; et al.: Blind digital watermarking of integer wavelet transform. Adv. Mater. Res. 433–440, 5962–5966 (2012) 8. Candes, E.J.; Wakin, M.B.: An introduction to compressive sampling. IEEE Signal Process. Mag. 25(2), 21–30 (2008) 9. Candes, E.; Romberg, J.: The restricted isometry property and its implications for compressed sensing. Computes Rendus Mathematique 346(9), 589–592 (2008) 10. Liu, X.; Yu, J.; Yue, Y.; et al.: A double encrypted digital image watermarking algorithm based on compressed sensing. J. Comput. Inf. Syst. 10(12), 5113–5120 (2014) 11. Xiao, D.; Cai, H.; Wang, Y.; et al.: High-capacity separable data hiding in encrypted image based on compressive sensing. Multimed. Tools Appl. (2015). https://doi.org/10.1007/s11042-015-2922-9 12. Makbol, N.M.; Khoo, B.E.: Robust blind image watermarking scheme based on redundant discrete wavelet transform and singular value decomposition. Int. J. Electron. Commun. 67(2), 102–112 (2013) 13. Vatsa, M.; Singh, R.; Noore, A.: Feature based RDWT watermarking for multimodal biometric System. Image Vis. Comput. 27(3), 293–304 (2009) 14. Sweldens, W.: The lift scheme: a custom design construction of biorthogonal wavelets. Appl. Comput. Harmon. Anal. 3(2), 186– 200 (1996) 15. Candès, E.; Romberg, J.; Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006) 16. Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006) 17. Chen, X.; Sun, X.; Sun, H.; et al.: Histogram shifting based reversible data hiding method using directed-prediction scheme. Multimed. Tools Appl. 74(15), 5747–5765 (2015) 18. Gadelmawla, E.S.: A vision system for surface roughness characterization using the gray level co-occurrence matrix. NDT & E Int. 37(7), 577–588 (2004) 19. Wang, Z.; Bovik, A.C.; Sheikh, H.R.; et al.: Image quality assessment: from error visibility to structural similarity. IEEE Trans. Image Process. 13(4), 600–612 (2004)
123
Arab J Sci Eng 20. Pan, J.-S.; Duan, J.-J.; Li, W.: A dual watermarking scheme by using compressive sensing and subsampling. Intell. Data Anal. Appl. 370, 381–389 (2015) 21. Xiao, Di; Deng, M.; Zhu, X.: A reversible image authentication scheme based on compressive sensing. Multimed. Tools Appl. 74, 7729–7752 (2015) 22. Singh, S.; Singh, R.; Siddiqui, T.J.: Singular value decomposition based image steganography using integer wavelet transform. In:
123
Thampi, S., Bandyopadhyay, S., Krishnan, S., Li, K.C., Mosin, S., Ma, M. (eds.) Advances in Signal Processing and Intelligent Recognition Systems. Advances in Intelligent Systems and Computing, vol. 425, pp. 593–601. Springer, Cham (2016) 23. Pan, J.-S.; Li, W.; Yang, C.-S.; et al.: Image steganography based on subsampling and compressive sensing. Multimed. Tools Appl. 74(74), 9191–9205 (2015)