Advanced
Reversible Watermarking Based on Compensation
Reversible Watermarking Based on Compensation
Journal of Electrical Engineering and Technology. 2015. Jan, 10(1): 422-428
Copyright © 2015, The Korean Institute of Electrical Engineers
This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/)which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : April 07, 2014
  • Accepted : September 18, 2014
  • Published : January 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xiaochao Qu
Graduate School of Information Security, Korea University, Korea. ({quxiaochao, suahnkim}@gmail.com)
Suah Kim
Graduate School of Information Security, Korea University, Korea. ({quxiaochao, suahnkim}@gmail.com)
Hyoung Joong Kim
Corresponding Author: Graduate School of Information Security, Korea University, Korea. (khj-@korea.ac.kr)

Abstract
This paper proposes a high performance reversible watermarking (RW) scheme based on a novel compensation strategy. RW embeds data into a host image by modifying its pixel values slightly. It is found that certain modified pixels can be compensated to their original values during the proposed embedding procedure. The compensation effect in the RW scheme can improve the marked image quality significantly. By incorporating the pixel selection method, a higher quality image is obtained, which is verified by extensive experiments.
Keywords
1. Introduction
Reversible watermarking (RW) hides data into a host image by modifying pixel values, and the distortion caused by embedding can be eliminated in the extracting process. As a result the embedded data can be extracted and the original host image recovered perfectly.
Difference expansion (DE) in [1] and histogram Shifting (HS) in [2] are two pivotal methods due to their large data embedding capacity and high quality of the marked image. Many improvements have been proposed based on DE and HS, such as prediction error expansion (PEE) [3] , invariability and adjustment on pixel pairs [4] , better location map construction [5] , double-layered embedding and sorting [6] , adaptive embedding [7] , histogram modification of pixel differences [8 , 9] , interpolation error histogram shifting [10] and the recently proposed two dimensional histogram shifting methods [11 , 12] . The above mentioned RW schemes are categorized as RW scheme without compensation because of the modification to host image can only be recovered after extracting data from the marked image.
In this paper, we propose a novel RW scheme with compensation which can recover parts of marked image back to original host image during the embedding procedure. In embedding procedure, each pixel is utilized for embedding data 0, 1 or 2 times, where the number of embedding is determined by the difference value between two pixels. The superiority of our scheme is that the distortion to the host image is reduced by embedding twice to certain pixels, and in the meantime, the embedding capacity is increased. However, a very large distortion could be caused by embedding to one pixel twice in most RW schemes without compensation. To further improve the marked image quality, a pixel selection scheme is incorporated into data embedding procedure. The pixels in smooth regions of the host image are used with priority, which reduces the distortion significantly. In the experiment section, the performance comparison of our proposed method with other pixel difference modification based methods demonstrates the huge effect of the novel compensation strategy. The further comparison of our method with three other state-of-the-arts methods shows that the proposed method is very effective for most test images.
The rest of this paper is organized as follows. The proposed scheme is described in section 2. Extensive experiments compare the proposed scheme with other five schemes in section 3. The conclusion is in the last section.
2. The Proposed Method
The data embedding procedure is introduced following the data extracting procedure, then we show how the overhead information is constructed which guarantees the success of blind extraction.
- 2.1 Embedding procedure
Assume the host image I is an eight-bit grayscale image with gray-level range [0, 255]. Let ( x , y ) be a pair of pixels. The half difference (denoted by d h ) between ( x , y ) is computed as
PPT Slide
Lager Image
The
PPT Slide
Lager Image
is the floor operation which rounds down the value to the next lowest integer value. To embed a data bit b belonging to {0, 1}, ( x , y ) should be transformed into ( x' , y’ ) according to the values of d h and b . The embedding rules are in Table 1 .
Embedding rules
PPT Slide
Lager Image
Embedding rules
When d h is equal to 0, a bit b can be embedded. Otherwise d h is increased by 1 or unchanged. Notice that for all cases, x stays unchanged or increased by 1 and y stays unchanged or decreased by 1. Assume ( x , y , z ) are three consecutive pixels, first we try to embed data into ( x , y ), so y becomes to y' which may be y or y - 1. Then we try to embed data into ( y' , z ), so y' becomes to y ″ which may have the value y' or y' +1. The possible value changes of y are summarized into Table 2 . When y is decreased by 1 and y' is increased by 1, y ″ is recovered to the original value of y . It shows that after two embedding, the value of y is recovered.
Possible changes ofy
PPT Slide
Lager Image
Possible changes of y
Notice that when d h is negative, we skip it without embedding data. The reason is that negative d h has different modification direction for ( x , y ), where x may be decreased and y may be increased. Assume there is a positive d h followed by a negative d h , then the middle pixel may be modified in one direction by two times, which will lead to large distortion. To summarize the possible number of embedding for each pixel, we denote d h 1 and d h 2 as the half difference between ( x , y ) and ( y' , z ), respectively. If d h 1 and d h 2 are both negative, then there is no embedding for y . If d h 1 and d h 2 are non-negative and negative and vice versa, then there is one embedding for y . If dh1 and dh2 are both non-negative, there are two embedding.
From another perspective, the proposed difference modification methods can be described with histogram shifting as in [9] . In the proposed method, only the peak 0 is used for embedding data. Any histogram bin that is bigger than 0 is shifted to right by 1. On the other hand, any negative histogram bin remains unmodified. However, the difference used in our method is quite different with [9] . The peak 0 in our method is composed of 0 and 1 in [9] . Therefore, our histogram peak is much higher than that of [9] . The negative histogram bin is not modified in our method, whereas most of the negative histogram bin in [9] will be modified, which causes large distortion. Another advantage of our proposed method is that the consecutive non-positive histogram bin can have compensation effect. In the experiment section, extensive experiments are conducted to show the superiority of the proposed method.
In each embedding for ( x , y ), the embedding procedure has the tendency to increase the value of x and decrease the value of y . When y is used for the second embedding in ( x , y , z ), its value has been modified to y' . In order to approximate the original d h between ( y , z ), Eq. (1) is modified to
PPT Slide
Lager Image
The first pixel in a pair is added by 1 when calculating d h to eliminate the value decrease caused by the previous embedding.
As shown in Table 1 , only d h with value 0 can be used for embedding. The d h which is bigger than 0 is increased by 1 and no data is embedded. For natural images, the smooth region tends to generate d h with smaller value than the rough region. Thus we incorporate a technique called pixel selection into our scheme to further improve the performance, which only selects the relatively smooth regions in the host image to use. A smoothness value for ( x , y ) is calculated by using its neighbor pixels. The locations of the neighboring pixels is shown in Fig. 1 . The smoothness value is computed as
PPT Slide
Lager Image
The neighboring pixels of (x, y) including n1 to n7
PPT Slide
Lager Image
In the embedding procedure, only those pixel pairs with smoothness value smaller than a threshold T will be utilized. The largest possible value for T is 255 × 5=1,275, so 11 bits are needed to record T . The value of T needs to be selected as in [7] to be the smallest value under which the embedding capacity is large enough for the to-be-embedded data.
The complete embedding procedure is as follows:
  • 1. Assume the size of host imageIisW×H, scanIinto a vectorSin raster-scan order (column-wise or row-wise).
  • 2. Iterate from the first pixel inS, calculate the difference between (Si,Si+1), where 1 ≤i≤W×H-1, and embed data into the possible pixel pairs with smoothness valuesmallerthan thresholdT.
  • 3. Embed theoverheadinformation into the firstNpixels’ least significant bit (LSB) and the LSBs from the firstNpixels are embedded into other pixels. (The detailed process is described in section2.3.)
  • 4. TransformS backtoI.
An embedding example is given in Fig. 2 . In the embedding process, there are three different kinds of pixel can appear which are defined separately. The modified pixel, unmodified pixel and recovered pixel are defined as p m (red color), p u (blue color) and p r (green color), respectively.
PPT Slide
Lager Image
Left: embedding example, from up to down. Right: extracting example, from down to up
- 2.2 Extracting procedure
The extracting procedure is the reverse of embedding procedure. For each pixel pair ( x' , y' ), calculate d h' . Then the embedded data b can be extracted and ( x' , y' ) is transformed back to the original value ( x , y ). The extraction rules are shown in Table 3 .
Extracting rules
PPT Slide
Lager Image
Extracting rules
The complete extraction procedure is as follows:
  • 1. Extract the first pixel’s LSB and determine the scan order. Scan the marked imageIinto vectorSby the same manner as in the embedding procedure.
  • 2. Extract complete overhead information from the firstNpixels’ LSB values.
  • 3. The extraction starts from the last used pixel pair and iterate to the first pixel pair by the reverse of embedding order. Calculate thedh'and smoothness value for each pixel pair. If the smoothness value is smaller thanT, extract data according toTable 3. The firstNpixels’ LSB values are then recovered using the extracted data.
  • 4. TransformSback to imageI.
An extracting example is given in Fig. 2 . Remark that the extracting order is the reverse of the embedding order.
- 2.3 Overhead information
The modification of pixels in the host image may cause overflow and underflow problems, where the pixel values are out of the gray-scale range [0, 255]. A location map is needed to record the pixels’ locations where overflow and underflow may occur. Scan the host image, record the locations of pixels with value 0 or 255 because the embedding procedure can only modify pixel values at most by 1. Each position needs log 2 ( W × H ) bits. For most natural images, there are not so many pixels with value 0 or 255, so the location map size is very small.
Some other information is also needed for blind extraction such as the last used pixel pair location (log 2 ( W × H ) bits), threshold for smoothness value T (11 bits), scan order (1 bit). The scan order bit is located as the first bit in the overhead information. Least significant bit (LSB) replacement is utilized where the first N pixels’ LSBs are replaced with overhead information and those N LSBs are embedded together with the payload data.
3. Experiment
The performance of reversible data hiding method is usually evaluated by the embedding capacity (EC) and the quality of the marked image. For measuring embedding capacity, bits per pixel (bpp) is the most popular metric which counts how many bits can be embedded into one pixel. Another popular metric to measure the embedding capacity is the number of embedded bits. For measuring marked image quality, the peak signal-to-noise ratio (PSNR) value is commonly used which is determined by the mean square error between the cover image and the marked image. In the following experiment, both bpp and the number of embedded bits are utilized.
The first experiment in this paper is carried out using images of SIPI image database [13] . Six test images with size 512 ×512 are used as shown in Fig. 3 .
PPT Slide
Lager Image
Six test images, from left to right and top to down, Lena, Baboon, F16, Barbara, Boat and Peppers.
To show the compensation effect of the proposed method, the distributions of p m , p u and p r are calculated. The gain of our compensation method depends on the number of p r and the more p r , the better of the marked image quality. The distribution of p m , p u , and p r for Lena is shown in Fig. 4 . The pixel distributions of all test images are summarized in Table 4 . About 20 to 30 percent of pixels are p r that are successfully compensated to their original values. Together with p u , around 50 percent of pixels stays unmodified after embedding data which can produce a peak signal-to-noise ratio (PSNR) value for marked image around 10 × log 10 (255 × 255/0.5) = 51.14dB.
PPT Slide
Lager Image
Pixel distribution for Lena. pm is red, pu is blue and pr is green.
Pixel distribution (%)
PPT Slide
Lager Image
Pixel distribution (%)
We then compare our method with [4] and [9] as shown in Table 5 . Both methods in [4] and [9] embed data by using pixel difference modification, which is similar with the proposed method. The superiority of the proposed method compared with [4] and [9] is thus mainly due to the compensation effect. The embedding capacity in Table 5 is the largest number of bits that can be embedded under the biggest modification of 1 to the pixel values of host image. The PSNR value is guaranteed to be above 48.13 dB [2] . The proposed method 1 and 2 are implemented using Eqs. (1) and (2), respectively. As can be seen in Table 5 , the proposed method 2 has larger embedding capacity than the proposed method 1 for all test images. Our method can embed much more bits than [4] and with higher marked image quality. For example, the proposed method 1 can embed 48,731 bits into Lena with PSNR 50.83 dB, their method can only embed 38,562 bits with PSNR 48.82 dB. Li et al. [9] can actually embed more number of bits than our method but their marked image quality is much lower than ours. The embedding capacity difference is less than 2,000 bits between proposed method 2 and [9] , but the proposed method 2 has the PSNR values 2 to 3 dB higher than [9] in most images. From the performance comparisons between the proposed method and [4 , 9] , it clearly validates the effectiveness of our compensation method.
The comparison of embedding capacity (EC via number of bits) and PSNR value (dB).
PPT Slide
Lager Image
The comparison of embedding capacity (EC via number of bits) and PSNR value (dB).
The incorporation of pixel selection can further improve the proposed methods to have comparable performance with the state-of-the-arts reversible watermarking methods. To demonstrate the superiority of the proposed scheme, we compare it with the methods in [6 , 7] , and [10] as shown in Figs. 5 - Fig. 10 . It can be seen that our scheme has comparable performance with other three methods for all test images and has the best performance for most test images. For the test image Boat, our scheme clearly outperforms the other three methods. Notice that the methods in [6 , 7] and [10] all use complicated predictors to predict pixel value, then, the data is embedded into prediction errors. For example, interpolation is used in [6] , rhombus pattern prediction is used in [7] and gradient adaptive prediction is used in [10] . The prediction errors are usually smaller than pixel difference which helps prediction errors based methods perform better than pixel difference based methods. However, the above experiment shows that our proposed pixel difference based method performs better than prediction error based methods by using a clever compensation embedding method. The compensation effect in our proposed method greatly improves the performance.
PPT Slide
Lager Image
Embedding capacity and PSNR of Lena
PPT Slide
Lager Image
Embedding capacity and PSNR of Baboon
PPT Slide
Lager Image
Embedding capacity and PSNR of F16
PPT Slide
Lager Image
Embedding capacity and PSNR of Barbara
PPT Slide
Lager Image
Embedding capacity and PSNR of Boat
PPT Slide
Lager Image
Embedding capacity and PSNR of Peppers
The second experiment evaluates the proposed method on two larger image data set. The first one is the Kodak image data set [14] which contains 24 color images. The second one is the BossBase image data set [15] that contains 10,000 gray-scale images. The BossBase image data set is originally used as a large scale standard data set for evaluating steganalysis methods. Fig. 11 shows the performance comparison of the proposed method with [4] and [9] with embedding 10,000 bits into each image. It can be seen that the proposed method outperforms [4] and [9] with big margin for most of the images.
PPT Slide
Lager Image
Performance comparisons of Kodak data set.
To compare the performance on the BossBase data set, we calculate the difference of PSNR for each image with embedding 10,000 bits and draw an occurrence histogram. The occurrence histogram shows the distribution of the PSNR difference. A better method should have more positive PSNR difference than negative PSNR difference. Figs. 12 and Fig. 13 shows the histogram of PSNR difference between the proposed method and [4 , 9] , respectively. It can be seen that most of the PSNR difference between our method and the other two methods are positive. For example, Fig. 14 shows that the most occurred PSNR difference between the proposed method and [9] is 5 dB, which occupies more than 16% of the PSNR difference distribution.
PPT Slide
Lager Image
Distribution of PSNR difference between the proposed method and [4] on the database of Boss Base.
PPT Slide
Lager Image
Distribution of PSNR difference between the proposed method and [9] on the database of Boss Base.
4. Conclusion
In this paper, a novel reversible watermarking method using compensation is proposed. This method can recover some parts of image during the embedding procedure by compensation, where the second embedding does not introduce distortion but reduce the overall distortion. The obtained marked image has very high image quality.
Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2012015587). This work was supported by the ICT R&D program of MSIP/IITP. [2014 (I5501-14-1007), 3D Smart Media/Augmented Reality Technology, Korea-China-Japan-Russia Cooperation International Standardization]. This research was supported by the MKE(The Ministry of Knowledge Economy), Korea, under the “ITRC” support program supervised by the NIPA(National IT Industry Promotion Agency) (NIPA-2010-C1090-1001-0004). This research was supported by Korea University.
BIO
Xiao Chao Qu He received B.S degree in computer science and technology from Harbin Institute of Technology, China in 2009. He is currently pursuing the Ph.D. degree in Korea University. His research interests are reversible watermarking, image processing and pattern recognition.
Suah Kim He received B.M degree in Combinatorics and Optimization from University of Waterloo in 2012. He is currently pursuing the Masters/Ph.D degree in information security in Korea University. His research interests include network forensics, data hiding, and CAPTCHA security.
Hyoung Joong Kim He is currently with the Graduate School of Information Security, Korea University, Korea. He received his BS, MS, and PhD from Seoul National University, Korea, in 1978, 1986, and 1989, respectively. He was a professor at Kangwon National University, Korea, from 1989 to 2006. He was a visiting scholar at University of Southern California, Los Angeles, USA, from 1992 to 1993. His research interests include data hiding such as reversible watermarking and steganography.
References
Jun Tian 2003 “Reversible Data Embedding Using a Difference Expansion,” IEEE Trans. Circuits Syst. Video Technol 13 (8) 890 - 896    DOI : 10.1109/TCSVT.2003.815962
Ni Zhicheng , Shi Yunqing , Ansari Nirwan , Su Wei 2006 “Reversible Data Hiding,” IEEE Trans. Circuits Syst. Video Technol 16 (3) 354 - 362    DOI : 10.1109/TCSVT.2006.869964
Thodi Diljith , Rodriguez Jeffrey 2007 “Expansion Embedding Techniques for Reversible Watermarking,” IEEE Trans. Image Process 16 (3) 721 - 730    DOI : 10.1109/TIP.2006.891046
Weng Shaowei , Zhao Yao , Pan Jeng-Shyang , Ni Rongrong 2008 “Reversible Watermarking Based on Invariability and Adjustment on Pixel Pairs,” IEEE Signal Process. Lett 15 721 - 724    DOI : 10.1109/LSP.2008.2001984
Kim Hyoung Joong , Sachnev Vasiliy , Shi Yun Qing , Nam Jeho , Choo Hyon Gon 2008 “A Novel Difference Expansion Transform for Reversible Data Embedding,” IEEE Trans. Inf. Forensics Security 13 (3) 456 - 465
Sachnev Vasiliy , Kim Hyoung Joong , Nam Jeho , Suresh Sundaram , Shi Yun Qing 2009 “Reversible Watermarking Algorithm Using Sorting and Prediction,” IEEE Trans. Circuits Syst. Video Technol 19 (7) 989 - 999    DOI : 10.1109/TCSVT.2009.2020257
Li Xiaolong , Yang Bin , Zeng Tieyong 2011 “Efficient Reversible Watermarking Based on Adaptive Prediction-Error Expansion and Pixel Selection,” IEEE Trans. Image Process 20 (12) 3524 - 3533    DOI : 10.1109/TIP.2011.2150233
Tai Wei Liang , Yeh Chia Ming , Chang Chin Chen 2009 “Reversible Data Hiding Based on Histogram Modification of Pixel Differences,” IEEE Trans. Circuits Syst. Video Technol 19 (6) 906 - 910    DOI : 10.1109/TCSVT.2009.2017409
Li Yu Chiang , Yeh Chia Ming , Chang Chin Chen 2010 “Data Hiding Based on the Similarity Between Neighboring Pixels With Reversibility,” Digit. Signal Process 20 (4) 1116 - 1128    DOI : 10.1016/j.dsp.2009.10.025
Luo Lixin , Chen Zhenyong , Chen Min , Xiong Zhang 2010 “Reversible Image Watermarking Using Interpolation Technique,” IEEE Trans. Inf. Forensics Security 5 (1) 187 - 193    DOI : 10.1109/TIFS.2009.2035975
Li Xiaolong , Zhang Weiming , Gui Xinlu , Yang Bin 2013 “A Novel Reversible Data Hiding Scheme Based on Two Dimensional Difference Histogram Modification,” IEEE Trans. Inf. Forensics Security 8 (7) 1091 - 1100    DOI : 10.1109/TIFS.2013.2261062
Ou Bo , Li Xiaolong , Zhao Yao , Ni Rongrong , Shi Yun Qing 2013 “Pairwise Prediction-Error Expansion for Efficient Reversible Data Hiding,” IEEE Trans. Image Process 22 (12) 5010 - 5021    DOI : 10.1109/TIP.2013.2281422
[Online]. Available:
[Online]. Available:
[Online]. Available: