Reversible Data Hiding for Btc-compressed Images Based on Bitplane Flipping and Histogram Shifting of Mean Tables

INTRODUCTION

Data hiding (Rabah, 2004) is a technique to embed copyright information or secret information into images, audio, video or 3D meshes without perceivable degradation. By and large, data hiding schemes can be classified into two categories, irreversible data hiding and reversible data hiding. Irreversible data hiding schemes (Xiao et al., 2009; Luo et al., 2011) can make the hidden data imperceptible but the distortions induced in the host signal are inevitable and irreversible. However, in reversible data hiding schemes (Hong et al., 2009, 2010), the secret data are embedded in a lossless manner such that one can completely recover both the hidden data and the original host signal. In some special application fields such as military, medical and forensic areas, it is necessary to recover the host image with no distortion after the extraction of hidden data. Therefore, reversible data hiding has become a hot research branch now-a-days.

Reversible data hiding for images can be classified into spatial-domain schemes and compressed-domain schemes. The first reversible data hiding scheme in the spatial domain includes an encoding method that embeds the authentication stamp in the digital block and a decoding method that retrieves the meta-data from an authenticated digital block and allows restoration of the original data block if desired (Barton, 1997). The generalized LSB (Least Significant Bit) modification based reversible data hiding algorithm (Celik et al., 2002) can losslessly recover the cover signal by compressing distortion-susceptible portions of the signal and transmitting these compressed data as a part of the embedded payload. The famous difference expansion based reversible data embedding method (Tian, 2003) explores the redundancy in the digital content to achieve the reversibility. However, the main drawback is the unforeseen but necessary location map. The reversible watermarking scheme proposed by Thodi and Rodriguez (2004) utilizes the correlation inherent among the neighboring pixels, where data embedding is done by expanding the prediction-error values. The high-capacity reversible watermarking algorithm for colored images proposed by Alattar (2004) first calculates the differences between every two neighboring pixels in a quad in a predefined order and then hides triplets of bits in the difference expansion of quads of adjacent pixels.

Since most digital images are stored in compressed forms, such as JPEG, JPEG2000, Vector Quantization (VQ) and Block Truncation Coding (BTC), it is necessary to research and develop compressed-domain reversible data hiding techniques. Here, the reversibility indicates that the compressed image can be completely recovered after the extraction of hidden data. That is, not the original image but its compressed version serves as the host signal. BTC is an efficient lossy image compression technique (Lu et al., 2002) that was first proposed by Delp and Mitchell (1979). It divides the original images into blocks and then uses a quantizer to reduce the number of grey levels in each block whilst maintaining the same mean and standard deviation. Another variation of BTC is Absolute Moment Block Truncation Coding (AMBTC) (Hong et al., 2008) that was first proposed by Lema and Mitchell (1984) in which instead of using the standard deviation the first absolute moment is preserved along with the mean. In the original AMBTC method, the MxN sized 256-grayscale image X is first divided into many non-overlapping mxn-sized blocks, i.e., X = {x^(ij), 1≤i≤M/m, 1≤j≤N/n}. The pixels in each block are individually quantized into two-level outputs, where the mean value of pixels in each block x^(ij) = {x^(ij)_uv, 1≤u≤m, 1≤v≤n} is taken as the one-bit quantizer threshold t_ij, i.e.,:

(1)

The two output quantization levels can be calculated as follows:

(2)

(3)

where, l_ij and h_ij denote the low mean and the high mean of block x^(ij), respectively q_ij stands for the number of pixels that are not less than the mean value t_ij. If q_ij = mxn, we have l_ij = h_ij = t_ij. Then a two-level quantization is performed for all pixels in the block to form a bitplane p_ij such that 0 is stored for the pixels whose values are less than the mean and the rest of the pixels are presented by 1. The image is reconstructed at the decoding phase from the bitplane by assigning the value l_ij to 0 and h_ij to 1. Thus a compressed block appears as a triple (l_ij, h_ij, p_ij), where l_ij, h_ij and p_ij denote the low mean, the high mean and the bitplane of block x^(ij), respectively. Figure 1 gives an example of encoding and decoding an image block based on AMBTC. In fact, if we gather all high means of all blocks, we can obtain a matrix that is called high mean table H = {h_ij, 1≤i≤M/m, 1≤j≤N/n}. Similarly, we can obtain the low mean table L = {l_ij, 1≤i≤M/m, 1≤j≤N/n} by gathering all low means while all bitplanes can construct a bitplane sequence P = {p_ij, 1≤i≤M/m, 1≤j≤N/n }.

Fig. 1:	An example of encoding a block x(ij) by the triple (lij, hij, pij)

AMBTC is computationally simpler than BTC. Although the original BTC is a fast encoding scheme, the bit rate (typically 2 bpp) is much higher than JPEG and VQ. In order to reduce the bit-rate many techniques have been introduced in BTC, such as median filtering, adaptive coding (Nasiopoulos et al., 1991), DCT-BTC (Wu and Coll, 1991) and VQ (Mohamed and Fahmy, 1995).

In the past ten years, several data hiding schemes for BTC compressed gray-level images have been proposed. The first work was proposed by Lu et al. (2002), where the robust watermark is embedded by modifying the VQ-BTC encoding process according to the watermark bits. In study of Lin and Chang (2004), a data hiding scheme for BTC compressed images was proposed by performing LSB substitution operations on BTC high and low means and performing the minimum distortion algorithm on BTC bitplanes. In study of Chuang and Chang (2006), a hiding scheme was proposed to embed data in the BTC bitplanes of smooth regions. However, above three works are not reversible. The first reversible data hiding scheme for BTC-compressed gray-level images was proposed by Hong et al. (2008). As we know, if we exchange l_ij and h_ij in the compressed triple of block x^(ij), we only need to flip the bitplane p_ij into in order to obtain the same reconstructed block. Based on this idea, the embedding process of Hong et al. (2008) scheme can be illustrated as follows: Firstly, each image block is compressed by AMBTC resulting in the compressed codes (l_ij, h_ij, p_ij). Secondly, all embeddable blocks with l_ij<h_ij are found, that is to say, the block with l_ij≤h_ij is non-embeddable. Thirdly, for each embeddable block, if the bit to be embedded is 1, then the compressed code is changed from (l_ij, h_ij, p_ij) into (h_ij, l_ij, ). Otherwise, if the bit to be embedded is 0, then no operation is required. In other words, the secret bit 0 corresponds to the code (l_ij, h_ij, p_ij) and the secret bit 1 corresponds to the code (h_ij, l_ij, ). The secret data extraction process is very simple. Assume we receive the code (l’_ij, h’_ij, p’_ij), we only need to judge the relationship between l’_ij and h’_ij. If l’_ij>h’_ij, then the secret bit is 1; Else if l’_ij<h’_ij, the secret bit is 0; Otherwise, no secret bit is embedded. Although Hong et al. (2008) scheme is reversible, it doesn’t consider hiding data in the blocks with l_ij = h_ij. To overcome this problem, an improved reversible hiding scheme (Chen et al., 2010) has been proposed recently. To embed secret data in the blocks with l_ij = h_ij, Chen et al. (2010) introduced Chuang and Chang’s bitplane replacement idea (Chuang and Chang, 2006) to deal with the case l_ij = h_ij in Hong et al.’s bitplane flipping scheme. The embedding process of Chen et al. (2010) scheme can be illustrated as follows: Each image block is compressed by AMBTC resulting in the compressed codes (l_ij, h_ij, p_ij). For each block with l_ij<h_ij, if the bit to be embedded is 1, then the compressed code is changed from (l_ij, h_ij, p_ij) into (h_ij, l_ij, ). Otherwise, if the bit to be embedded is 0, then no operation is required. For the block with l_ij=h_ij, since the bitplane has no use in the reconstruction process, the whole bitplane can be replaced with mxn secret bits. The secret data extraction process is also very simple. Assume we receive the code (l’_ij, h’_ij, p’_ij), we only need to judge the relationship between l’_ij and h’_ij. If l’_ij>h’_ij, then the secret bit is 1; Else if l’_ij<h’_ij, the secret bit is 0; Otherwise, all mxn bits in the bitplane p’_ij are extracted as the secret bits.

From above, we can see that, existing data hiding schemes in the BTC domain have low capacity and may reduce the image quality. To both increase the hiding capacity and achieve the reversibility, this study has proposed an improved reversible data hiding for BTC-compressed images by further introducing the histogram shifting technique to BTC compressed data. Experimental results and a comparison with Hong et al. (2008) reversible hiding algorithm and Chen et al. (2010) reversible hiding algorithm have demonstrated the superiority of our proposed scheme.

THE PROPOSED SCHEME

We can see that Hong et al. (2010) bitplane flipping scheme and Chen et al. (2010) scheme can embed 1 bit information per block if there is no block with l_ij = h_ij. In order to embed more secret bits, after using Chen et al. (2010) scheme, we can further compose all high/low means as a high/low mean table and then introduce the histogram shifting technique to high and low mean tables. The proposed algorithm consists of three stages, i.e., the AMBTC compression stage, the data hiding stage and the data extraction and image recovery stage which can be illustrated as follows.

The AMBTC compression stage: This stage is a preprocessing stage before data hiding. The aim of this stage is to obtain the two mean tables and the bitplane sequence for later use. Given an MxN-sized 256 grayscale original image X, this stage can be expressed as follows:

The data hiding stage: With the mean tables H and L and the bitplane sequence P in hand, now we can introduce our reversible data hiding algorithm. Assume the secret bit sequence to be embedded is W = {w₁,w₂,…}. Before embedding, we perform the permutation operation on the secret bit sequence in order to enhance the security. Our embedding method is performed in two main steps, i.e., bitplane flipping and histogram shifting which can be illustrated detailedly as follows:

•	Step 1: We first perform the bitplane flipping technique on H, L and P to embed the first part of secret bits. For each image block with lij<hij, if the bit to be embedded is 1, then the element hij in H and the element lij in L are swapped and the bitplane pij in P is replaced by . Otherwise, if the bit to be embedded is 0, then no operation is required. For the block with lij = hij, since the bitplane has no use in the reconstruction process, the whole bitplane pij in P can be replaced with mxn secret bits. After this step, we get the modified mean tables and bitplane sequence denoted as H’, L’ and P’, respectively
•	Step 2: We further perform the histogram shifting technique on H’ and L’, respectively to embed the second part of secret bits. The detailed sub-steps can be illustrated as follows:
•	Step 2.1: Generate the histogram from H’
•	Step 2.2: In the histogram, we first find a zero point and then a peak point. A zero point corresponds to the grayscale value v which doesn’t exist in the given image. A peak point corresponds to the grayscale value u which has the maximum number of pixels in the given image
•	Step 2.3: The whole mean table is scanned in a sequential order. Assume u<v, the grayscale value of pixels between u (including u) and v (including v) is incremented by 1. This step is equivalent to shifting the range of the histogram, (u, v), to the right-hand side by 1 unit, leaving the grayscale value u empty
•	Step 2.4: The whole mean table is scanned once again in the same sequential order. Once a pixel with grayscale value of u is encountered, we check the secret bit to be embedded. If this bit is binary 1, the pixel value is incremented by 1. Otherwise, the pixel value remains intact
•	Step 2.5: After above sub-steps, we can get the final marked high mean table H”. Similarly, perform above sub-steps on the low mean table L’ to get the final marked low mean table L’. Note that we should record the u, v values for H and L, respectively as the overhead information

The decoding and extracting stage: Present data hiding scheme is reversible because we can recover the original mean tables and the bitplane sequence after data extraction and thus the original BTC-compressed image can be losslessly recovered. Given the marked mean tables H^w and L^w and the marked bitplane sequence P^w, our purpose is to extract the secret bit sequence and recover the original BTC compressed image, the extraction process as follows:

•	Step 1: Perform the reverse histogram shifting technique on Hw and Lw to extract the second part of secret bits and get the intermediate result Hr and Lr, respectively. The detailed sub-steps can be illustrated as follows:
•	Step 1.1: Scan the marked table Hw in the same sequential order as that used in the embedding procedure. If a pixel with its grayscale value v + 1 is encountered, the secret bit 1 is extracted. If a pixel with its value v is encountered, a secret bit 0 is extracted
•	Step 1.2: Scan the image again, for any pixel whose grayscale value is in the interval (u, v), the pixel value is subtracted by 1
•	Step 1.3: After above sub-steps, we can get the intermediate high mean table Hr. Similarly, perform above sub-steps on the marked low mean table Lw to get the intermediate low mean table Lr
•	Step 2: Perform the reverse bitplane flipping technique on Hr, Lr and Pw to extract the first part of secret bits and recover the BTC-compressed image data. For each triple (lrij, hrij, pwij), we only need to judge the relationship between lrij and hrij. If lrij>hrij, then the secret bit is 1 and lrij and hrij are swapped and the bitplane pwij is replaced by ; Else if lrij<hrij, the secret bit is 0; Otherwise, all mxn bits in the bitplane pwij are extracted as the secret bits, replace the bitplane pwij with mxn ‘1’ s

Based on above two steps, we can extract all secret bits and reconstruct the original BTC-compressed image, thus the whole reversible process is realized. Obviously, the improved scheme can increase the payload compared with Chen et al. (2010) scheme.