Dynamic Histogram Shifting for Reducing Distortion
in Image Embedding

V. Lavanya; G. Annapoorani

Dynamic Histogram Shifting for Reducing Distortion in Image Embedding

V. Lavanya¹, G. Annapoorani²

Student, Pervasive Computing Technologies, University College of Engineering, Tiruchirappalli (BIT campus), India
Assistant Professor, Department of Computer Science and Engineering, University College of Engineering, Tiruchirappalli (BIT campus), India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

In the recent years, lot of researches is taking place in the field of watermarking to establish more efficient reversible techniques. It is because always there is a need to protect the images of sensitive content such as the military or medical data. The existing system such as the Difference Expansion and Expansion Embedding are most commonly used techniques but suffers from undesirable distortion which makes these methods unsuitable or less reliable. A combination of two techniques pixel histogram shifting and dynamic predictive error histogram shifting are introduced as an attempt to improve the quality of the watermarked image.. The image is first classified invariantly to find which area of the image can be watermarked. On classifying the watermark bits are applied by direct histogram shifting or by shifting it dynamically. Two secret images are embedded into the same cover image considering the odd and even columns of the pixel matrix. This method inserts the payload in the textured area and thus reduces the distortion and it also increases the embedding capacity of the cover image.

Keywords

watermark; histogram shifting; predictive error

INTRODUCTION

Information exchange in olden days was only by text messages but due to the development in the field of technology now-a-days the transmission of data is in the type of multimedia. Information is being transferred as digital images or videos etc. This was a tremendous leap that enhanced the data transmission process but at the same time the multimedia transmission was insecure because it can easily be retrieved and duplicated. Thus a technique to safeguard the images and videos that are being transmitted was inevitable. Most of the military and medicals records require a high degree of security while being transferred because these documents contains lot of confidential information which should not be exposed without the concerned person’s permission. The most prominent technique used to maintain the integrity of these images is the watermarking method.

The word watermarking was procured from a Greek word ‘Wessmark’. Watermarking technique was introduces to hide data inside the digital images to avoid being misused by the inappropriate users. There are two types of watermarks, visible and invisible. Visible watermark is where a piece of information is deliberately displayed over the digital image. For example it may be a company’s name or logo over the image. These watermarks can be applied in areas of text documents, on digital images or on multimedia files. In the second type, the information does not appear on the images. It is meant to hide the secret information inside another image to maintain security. Thus as the type name itself says the watermark is invisible but its existence can be determined by using watermark detection or extraction algorithms. Thus it is always necessary to develop more complicated and efficient watermarks such that the presence of these watermarks cannot be determined by the hackers. Implementing the watermarking technique includes two processes, encoding and decoding. In the watermarking process, first a random area of the image is selected which is then converted in to a matrix by obtaining its pixel values. Usually grayscale image is taken since the complexity is less to calculate for a single value. These values in decimal are converted into binary values. The secret image to be embedded is also converted into a matrix of binary values which represent their pixels. Then both the matrices perform an OR operation to obtain the watermark. Thus an image is hidden using a watermarking technique. This process of hiding invisible information (watermark) into an image is called as encoding. Similarly the process of extracting the hidden information from the image is called as decoding. It can only be decoded with decoding algorithm. There are other situations where the modified part of the image is not only identified but it also has to be recovered. Thus the process of embedding has to be reversed to obtain the original state of the modified image. These types of techniques are called the reversible data embedding techniques. The watermarking technique maintains the integrity of the image whereas the reversible technique solves the content authentication problem.

Various watermarking techniques have been introduced in the past decade, with the main aim of protecting the information sensitive images in which even slight modification may affect or completely change the sense of the image [6]. Due to this constraint there emerged a need where the retrieving of the secret image by removing the watermark must be exactly the original image that was embedded in the beginning.

RELATED WORK

Tian et al envisioned a new technique known as the DE [1] which explores the redundancy and discovers more space for storage in the image content. The DE technique was used so that the invisible data can be embedded in to the digital images reversibly. The visual quality and the payload capacity are improved than the previous methods and the computational complexity was also less. They applied it for the grayscale images and further the payload was embedded in the difference of the pixel values. The average (l) and the difference (h) of the pixel values are first calculated. The bit (b) to be embedded is appended at the LSB of the difference value (h) in the binary form. New difference value (h`) is obtained. Now the new pixel values (x`, y`) are obtained using the average and the new difference value. This process is completely reversible and the bit embedded can be reproduced finally.

Thodi et al generalized the DE scheme which gave rise to the EE[4] modulation which was developed to apply the LSB substitution to samples that cannot be expanded due to the signal dynamic limits in order to preserve the image quality. They proposed a new reversible data embedding technique called the prediction-error expansion. Predictionerror expansion technique and the histogram shifting method is merged to form a effective method for data embedding thus the quality of the watermarked image is significantly improved.

The algorithm introduced by Ni et al [2] applies multiple pairs of the zero and peak points for the image embedding. This way the embedding process is completed. The payload is referred to as the data to be embedded in the cover image. If the payload is less than the actual capacity of the cover image then single pair of zero and peak points are used if it is more than the capacity then multiple pairs of zero and peak points are used. The grayscale values of the pixels between the zero and the peak points will be incremented or decremented by ‘1’ in the embedding process. This lead to the evolution of a well-known concept called the Histogram Shifting [2]. The ranges of classes of the histogram of the image are shifted by adding some gray values to the pixels. It creates a gap near the histogram maxima.

In the HS technique, the range of pixels is shifted based on the fixed magnitude (Δ), due to which a gap is created near the histogram maxima. The pixels belonging to the histogram maxima are shifted to the gap in order to embed a message bit ‘0’ and it is kept unchanged if the message bit ‘1’ is being embedded. The pixels that are shifted are basically called as the ‘carriers’ and the unchanged pixels are known as the ‘non-carriers’. Also the extractor while retrieving the original image has to know the exact positions of the pixels that have been shifted out of the dynamic range (underflows/overflows). This action requires a location map that explicitly denotes the pixels that has undergone the underflows or overflows, thereby reducing the watermark capacity. HS suffers a disadvantage where the modulation cannot be applied to uniformly distributed data.

To avoid the location map overhead Hu et al [5] studied the DE technique to provide a solution. In DE based data embedding there are mainly two parts of the data. The first part constitutes the payload and the second part of the data includes information that is needed for detection. Information such as the location map and the header file are included in the second part. To embed more amounts of data the size of the overflow map must be small. In order to make such a hiding this paper proposes a algorithm which enables the map to compress a greater extent. Thus is makes the embedding capacity of the cover image higher in spite of the presence of an overflow map. The predicted error is embeddable if the error does not cause an overflow or underflow problem.

PROPOSED ALGORITHM

The classical Histogram Shifting method is slightly modified in order to obtain a quality watermarked image. The histogram shifting here is dynamically applied. The cover image is first classified into regions where addition of watermark bits will lead to an invariant image from that of the original cover image. On identifying the two sets of regions histogram shifting is applied directly or applied dynamically. When histogram shifting is directly applied to pixels it is called the ‘pixel histogram shifting’ and when it is applied dynamically on prediction errors it is called ‘dynamic prediction error histogram shifting’. To predict these regions the prediction error Ex,y is calculated,

These modulations will modify only one pixel in the block that has been classified. Generally the watermarking introduces distortion. This distortion is reduced by the dynamic predictive error histogram shifting algorithms and it increases the quality of the embedded image. The block that is classified is considered to be 3X3 matrix with 9 pixel points. In the block the prediction errors for the pixel is calculated and then the watermark matrix which is a 9 value matrix is embedded.

Thus the process of embedding can be of two steps based on the Tmin and Tmax values. As this method is a reversible watermarking technique, the extraction process also takes place to obtain the secret image that has been embedded into the cover image. To extract the image the matrix already exists. That is the same block is used and the same matrix is taken for extraction process. The histogram shifting amplitude is the key factor for extracting the image and only by knowing this single parameter the exact original image can be extracted.

The payload is usually in the form of a binary sequence. The underflow and overflow problems are also considered and avoided in our proposed system. The delta gray values are added while shifting the pixels by using the pixel histogram shifting and thus the risk of overflow can be avoided. But even if the overflow occurs then it can also be handled as the message bit is encoded along which indicates the underflow or the overflow that has occurred and it also contains the information that is required to recover the pixels. This method can be applied to grayscale images because the range lies between 0 and 255 and thus the complexity is reduced.

The method proposed is aimed to reduce the distortion rate in the medical images prominently. As the technique is a reversible technique is performs the content authentication in order to verify the originality of the embedded image. The main advantage of the method is that since the distortion is less, it becomes a difficult task for the attackers to guess the presence of the secret image and thus security is provided for the confidential images. Also no complex transformations are used and thus the proposed method is a simple technique that provides efficient protection. The paper is aimed to achieve highest bit per pixel and less peak signal to noise ratio which will be explained in the later section of the paper. These modulations will modify only one pixel in the block that has been classified which makes it easy for the process to be reversible during the extraction.

The underflows/overflows are inevitable and hence occur in this process too but care has to be taken to manage the occurrence. For every pixel Pk a block of 3X3 pixels is considered for which a reference block is constructed. Pk (x,y) will be modulated which is the addition of the watermark bit to the pixel block. Due to this the reverence block remains invariant to the modulation. For a pixel Pk (x,y) PHS modulation is applied when its predictive error falls in the range less than the value Δ and greater than (2d-1) - Δ, where d is the bit depth image. In this type of modulation the pixels are shifted by adding Δ gray values thus there is no risk of an underflow whereas an overflow might occur.

Always the watermark is embedded along with the message flags indicating the occurrence of the underflow/overflow and also the information required to retrieve the original image pixels. Nevertheless, in some cases, the extractor can identify threshold values T^r_min and T^r_max different from T^r_min and T^r_max computed at the embedding stage. In fact, some watermarked pixels (or blocks) may be identified by the extractor as subject to underflow or overflow changing at the same time the threshold values in a way such as T^r_min T_min and T^r_max T_max If this change occurs the extractor needs to be informed of the original values of T_min and T_max so as to retrieve all watermarked pixels and recover the original image perfectly. In our system, flag bits that indicate the change of T_min and T_max as well as their original values are embedded along with the message and a two step insertion process is used. During the first step, T_min and T_max and a part of the message is embedded considering the values of T^r_min and T^r_max the decoder will find. The remaining portion of the message is embedded by modifying the last watermarkable pixels. On the recipient side, the extractor will extract the first part of the message based on T^r_min and T^r_max . It will get access to the rest of the information after a second reading step.

SIMULATION RESULTS

The performance is generally measured in the form of peak signal to noise ratio (PSNR) and the bit per pixel (bpp) values. The PSNR represents the amount of distortion between the image and the watermarked version and the bpp known as the capacity rate, is the bit message that is stored in each pixel of image. The method proposed is aimed to reduce the distortion rate in the medical images prominently. As the technique is a reversible technique is performs the content authentication in order to verify the originality of the embedded image.

The result for the proposed technique is given in the form of a table in terms of in terms of capacity and the image distortion depending on the pixel shifting magnitude Δ. As we can see that the capacities are higher compared to the existing techniques. The results produces for the medical images are approximately equal to that of the results obtained for the natural test images. Furthermore this method provides the best compromise of image quality preservation for the low and medium capacities.

CONCLUSION AND FUTURE WORK

The proposed reversible watermarking scheme combines two distinct modulations pixel histogram shifting and dynamic prediction error histogram shifting. The second modulation is the technique that is being used to reduce the distortion while increasing the payload capacity of the image. Even though the technique is enhanced, it is still weak and thus modifications performed will affect the watermark. One of the major upcoming challenges is about the robustness of the watermark.

Tables at a glance

Table 1

Figures at a glance


Figure 1	Figure 2	Figure 3

References

J. Tian, “Reversible data embedding using a difference expansion,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 8, pp. 890–896, Aug. 2003.

Z. Ni, Y. Q. Shi, N. Ansari, and S.Wei, “Reversible data hiding,” IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 3, pp. 354–362,Mar. 2006.

G.Xuan,Y.Q.Shi,C.Y.Yang,Y. Z. Zheng, D. K.Zou, and P. Q. Chai, “Lossless data hiding using integer wavelet transform and thresholdembedding technique,” in Proc. Int. Conf.Multimedia and Expo, 2005, pp. 1520–1523.

D.M. Thodi and J. J. Rodriquez, “Expansion embedding techniques for reversible watermarking,” IEEE Trans. Image Process., vol. 16,no. 3, pp. 721–730, Mar. 2007.

Y. Hu, H.-K. Lee, and J. Li, “DE-based reversible data hiding with improved overflow location map,” IEEE Trans. Circuits Syst. VideoTechnol., vol. 19, no. 2, pp. 250–260, Feb. 2009.

G. Coatrieux, C. Le Guillou, J.-M. Cauvin, and C. Roux, “Reversible watermarking for knowledge digest embedding and reliabilitycontrol in medical images,” IEEE Trans. Inf. Technol. Biomed., vol. 13, no. 2, pp. 158–165, Mar. 2009.

F. Bao, R. H. Deng,B.C.Ooi, andY. Yang, “Tailored reversible watermarking schemes for authentication of electronic clinical atlas,”IEEE Trans. Inf. Technol. Biomed., vol. 9, no. 4, pp. 554–563, Dec. 2005.

H. M. Chao, C. M. Hsu, and S. G. Miaou, “A data-hidding technique with authentication, integration, and confidentiality for electronicpatient records,” IEEE Trans. Inf. Technol. Biomed., vol. 6, no. 1, pp. 46–53, Mar. 2002.

L. Luo, Z. Chen, M. Chen, X. Zeng, and Z. Xiong, “Reversible image watermarking using interpolation technique,” IEEE Trans. Inf.Forensics Security, vol. 5, no. 1, pp. 187–193, Mar. 2010.

D. Coltuc, “Improved embedding for prediction-based reversible watermarking,” IEEE Trans. Inf. Forensics Security, vol. 6, no. 3, pp.873–882, Sep. 2011.

C. C. Lin, W. L. Tai, and C. C. Chang, “Multilevel reversible data hiding based on histogram modification of difference images,” PatternRecognit., vol. 41, pp. 3582–3591, 2008.

C. H.YangandM.H. Tsai, “Improving histogram-based reversible data hiding by interleaving predictions,” IET Image Process., vol. 4, no.4, pp. 223–234, Aug. 2010.

C. De Vleeschouwer, J.-F. Delaigle, and B. Macq, “Circular interpretation of bijective transformations in lossless watermarking for mediaasset management,” IEEE Trans.Multimedia, vol. 5, no. 1, pp. 97–105, Mar. 2003.

D. Coltuc and J.-M. Chassery, “Distortion-free robust watermarking: A case study,” in Proc. Security, Steganography, and Watermarkingof Multimedia Contents IX, San Jose, CA, 2007, p. 65051N-8.

V. Sachnev, H. J. Kim, J. Nam, S. Suresh, and Y.-Q. Shi, “Reversible watermarking algorithm using sorting and prediction,” IEEE Trans.Circuit Syst. Video Technol., vol. 19, no. 7, pp. 989–999, Jul. 2009.

H. J. Hwang, H. J. Kim, V. Sachnev, and S. H. Joo, “Reversible watermarking method using optimal histogram pair shifting based onprediction and sorting,” KSII, Trans. Internet Inform. Syst., vol. 4, no. 4, pp. 655–670, Aug. 2010.