Reversible Data Hiding in Encrypted Images based on Pixel Prediction and Bit-plane Compression

Reversible data hiding in encrypted images (RDHEI) receives growing attention because it protects the content of the original image while the embedded data can be accurately extracted and the original image can be reconstructed lossless. To make full use of the correlation of the adjacent pixels, this paper proposes an RDHEI scheme based on pixel prediction and bit-plane compression. Firstly, to vacate room for data embedding, the prediction error of the original image is calculated and used for bit-plane rearrangement and compression. Then, the image after vacating room is encrypted by a stream cipher. Finally, the additional data is embedded in the vacated room by multi-LSB substitution. Experimental results show that the embedding capacity of the proposed method outperforms the state-of-the-art methods.


I. INTRODUCTION
R EVERSIBLE data hiding (RDH) has attracted wide attention that it embeds additional data into multimedia. At the same time, the original medium can be reconstructed lossless and the embedded data can be accurately extracted. Therefore, RDH is widely utilized in many applications [1], such as reversible image processing, reversible visual transformation and reversible adversarial example described, etc. Many RDH algorithms in spatial images have been proposed and can be classified into three categories based on the different technologies: lossless compression [2] [3], histogram shifting [4]- [7], and difference expansion [8] [9]. Recently, with the widely used cloud storage and privacy protection, multimedia encryption may be implemented before transmission for the content-owner. Thus, reversible data hiding in encrypted images (RDHEI) [10] [11] has been proposed.
Generally, content-owner, data-hider, and receiver are three end-users of RDHEI [12]. The contents of the original image are protected by the encryption operation of the content-owner. The data-hider can embed additional data without knowing the contents of the original image. The permissions depend on the number of keys for the receiver. The data encryption key can accurately decrypt the extracted additional data, and the image encryption key can reconstruct the original image.
The RDHEI methods proposed in recent years mainly can be classified into two categories: vacating room after encryption (VRAE) [12]- [15] and reserving room before encryption (RRBE) [16]- [22], as shown in Fig. 1. For the VRAE methods, the local spatial correlation of the original image is utilized while the image is encrypted. But they can't achieve satisfied embedding capacity and some algorithms are irreversible or inseparable. The RRBE methods reserve room before image encryption based on the pixel correlation. Then, the reserving room is transferred into the encrypted image. Compared with the VRAE method, the RRBE algorithm makes full use of the pixel correlation of the original image and has a higher embedding capacity.
In [16], The RRBE scheme is first proposed. The least significant bits (LSBs) of some pixels are embedded into other pixels before encryption. The embedding capacity has great improvement compared with the traditional VRAE methods [11]- [13]. At the same time, additional data can be extracted accurately and images can be reconstructed. In [17], an estimation technique is proposed to reserve room before encryption. In order to further improve the embedding capacity of RDHEI, Chen et al. [18] proposed an RDHEI method based on bit-plane compression. Firstly, the bit-plane rearrangement (BPR) is implemented. Then, the rearranged bit-stream is compressed. Finally, the vacated room is used to embed additional data. Different from the bit-plane compression, several methods based on image marking [19]- [22] are also proposed. Puteaux et al. [19] proposed an RDHEI method based on the most significant bit (MSB) prediction. Firstly, the error label map recorded the non-embeddable pixels is embedded into the encrypted image. Then, the MSB of the available pixels is substituted by 1 bit additional data according to the error label map. Based on this method, an RDHEI of two-MSB prediction scheme is proposed in [20]. A parametric binary tree labeling method presented in [21] is used to distinguish the prediction errors. The data-hider can use the parameter to embed the additional data in the encrypted image. In another method proposed by Yin et al. [22], the binary sequence of the original pixel and the prediction error is sequentially compared from the MSB to the LSB. Then, the number of same bits is marked with Huffman coding. Finally, the multi-MSB is substituted by the additional data and the embedding capacity increases. Compared with the above method, the embedding capacity has increased. But the correlation of the adjacent pixels isn't fully utilized and embedding capacity can be further increased.
How to make full use of the correlation of the adjacent pixels? In this paper, an RDHEI scheme based on pixel prediction and bit-plane compression is proposed. At the content-owner end, the prediction error of the original image is first calculated.

A 1
Type label :00, Row by row, Row by row Rearranged: Type label :01, Row by row, Column by column Rearranged: Type label :10, Column by column, Row by row Rearranged: Type label :11, Column by column, Column by column Rearranged:A 1 A 3 A 2 A 4 C 1 C 3 C 2 C 4 B 1 B 3 B 2 B 4 D 1 D 3 D 2 D 4 (BSC) algorithms are implemented. The vacated room is used to embed additional data is embedded by the data-hider in the vacated room. Finally, the receiver can independently reconstruct the image or extract additional data according to the different keys. The bit-plane of the prediction error is compressed in the proposed method. Each bit of all pixels is fully utilized. Experimental results show that the proposed method outperforms the state-of-the-art methods.
The remainder of this paper is organized as follows: bitplane rearrangement and compression schemes [18] are briefly described in Section II. An RDHEI scheme based on pixel prediction and bit-plane compression is detailed introduced in Section III. Experimental results and the comparison are given in Section IV and Section V concludes this paper.

II. BIT-PLANE REARRANGEMENT AND COMPRESSION
In this chapter, the bit-plane rearrangement and the bitstream compression algorithms [18] are introduced. In order to make full use of the spatial correlation in the original images, the bit-planes divided into blocks are rearranged using four types. Section II-A gives detailed steps and example. Section II-B also gives detailed steps and example to introduce the bit-stream compression algorithm.

A. Bit-Plane Rearrangement
As we all know, the size of a natural image is relatively large. If each bit-plane of the image is traversed by raster scanning, the spatial correlation of the pixels is not fully utilized. Thus, in order to improve the compression rate, the bit-streams of the bit-plane are rearranged by block scanning in [18]. Firstly, the bit-planes are divided into blocks of the same size. Then, the bit-planes are rearranged by the four types. Taking Fig. 2 as an example to introduce the main step. The bit-plane is first divided into 2 × 2 blocks. Type label = 00 denotes that the traversing order of bits inside the block is row by row, and the order of blocks is also row by row. The rearranged bit-stream sequence is Type label = 01 represents that the traversing order of bits inside the block is row by row, and the order of blocks is column by column. The rearranged bit-stream sequence is The rearranged results of the other two types can also be obtained from the Fig. 2.

B. Bit-Stream Compression
After using the BPR algorithm, the rearranged bit-streams will have a large number of adjacent "0" or "1". Due to this characteristic, the BSC algorithm vacates more room to embedding additional data. Firstly, extracting the same bits sequence L from the rearranged bit-streams. Secondly, encoding L as a code word. Finally, the above operation is repeatedly performed for the subsequent sequence of rearranged bitstreams. The number of L determines the compression mode: Case 1: L < 4. L pre = 0, the value of L mid is the rearranged bit-streams of length L f ix that is intercepted backward from the current bit.
Case 2: L ≥ 4. L pre consists of l − 1 sequential 1 s and end with 0. L tai = 0 or 1, indicating the repeat bits. The values of l and L mid are calculated as follows: Where L pre , L mid and L tai denote prefix, middle and tail of C 1 . L f ix is a parameter and * is the floor operation. For example, as shown in Fig. 3, assume the uncompressed bit-streams is 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 and L f ix = 4 . In the first run process, firstly, the eleven 1 s is extracted. Then, 11 bits ≥ 4 bits, l = 3 can be calculated by Eq. (1) and L pre = 110. L mid = 011 can be calculated by Eq. (2). Since the values of these 11 bits are all 1, L tai = 1. Finally, C 1 is 1 1 0 0 1 1 1. The second run of two 0 s is extracted. Because of 2 bits < 4 bits, L pre = 0 and L mid = 00011. The third run of sixteen 0 s is encoded as 111000000. Finally, the 31 original bits are compressed into 21 bits, and the vacated room can be used to embed additional data.

III. PROPOSED METHOD
This paper proposes an RDHEI based on pixel prediction and bit-plane compression. As shown in Fig. 4, three stages consist of our method: 1) Vacating room and image encryption by the content-owner; 2) Data embedding by the data-hider; 3) Data extraction and image decryption by the receiver. In the first stage, to vacate more room, the prediction error of the original image is used for bit-plane rearrangement and compression in the proposed method. Section III-A gives a detailed introduction. Then, the image encryption is performed in Section III-B. In the second stage, the additional data is embedded in the vacated room that is generated in the first stage. For the receiver, the image can be recovered and the embedded data can be extracted, separately.
A. Vacating Room 1) Pixel Prediction: Consider an original image I of size m × n, the predicted value of each pixel can be calculated by the median edge detector (MED) [23]. As shown in Fig. 5, the predicted value px of current pixel x is calculated by its three neighboring pixels x 1 ,x 2 and x 3 . The predicted value and the predicted error of each pixel can be giving in the following: In this part, the decimal prediction error ex of the original image I is converted into 8 bits binary. Because the sign of the prediction error can be positive or negative, the maximum significant bit (MSB) is used as the sign marker bit, "1" denotes negative and "0" denotes positive. The absolute value of predictive error is converted into 7 bits binary by the Eq. (5). When the prediction error exceeds the range of [−127, 127], this pixel is marked as the overflow pixel and does not be changed. At the same time, its location is recorded as auxiliary information.
Where 1 ≤ i ≤ m and 1 ≤ j ≤ n, ex k (i, j) is the binary of corresponding bit. Taking the prediction error ex (1, 1) = −2 as an example, its binary of the absolute value is 0000010, so   2) Bit-plane Rearrangement and Compression: The BPR and the BSC algorithms are used for the 8 bits planes of the prediction error from the MSB plane to the LSB plane. Firstly, the MSB plane is rearranged using four types. Then, the shortest compressed bit-stream is selected from the four rearranged ways. At last, if the length of the compressed bitstream is longer than that of the original bit-stream, the bitplane is not compressed. If the length of the compressed bitstreams is less than that of the original bit-streams, the shortest compressed bit-streams is adopted.
As shown in Fig. 6, we take a bit-plane and type label = 00, 01 as an example. The length of the original bit-streams is 36 bits. Firstly, the bit-plane is divided into the block size of 3 × 3. When type label = 00, the traversing order of bits inside the block and inter-block are all row by row, and the rearrangement result is 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. The compressed length is 24 bits. When type label = 01, the traversing order of bits inside the block is row by row and inter-block is column by column. The compressed length is 31bits. Since 24 bits < 31 bits, the type label = 00 is adopted.
For a compressed bit-plane, as shown in Fig. 7, the flag denoted whether the bit-plane can be compressed and is marked by 1 bit. The rearrangement type use 2 bits to record. The gray region represents the compressed bit-streams, and the blank region denotes the vacated room. Then, all compressed bitstreams and uncompressed bit-plane are connected to generate new multi-MSB planes and all the vacated multi-LSB planes are complemented by 0. Auxiliary information includes the block size, the value of L f ix , and the number of overflow pixels. As shown in Fig. 8, auxiliary information is placed on the MSB plane, the number of compressed bit-streams is placed on the LSB plane. Finally, the compressed image containing embeddable room I c is calculated by Eq. (6).
Where 1 ≤ i ≤ m and 1 ≤ j ≤ n, x c (i, j) is the pixel of compressed image I c

B. Image Encryption
In the image encryption phase, generating a pseudo-random matrix H of size m × n by key K en . The pixel x c (i, j) of the compressed image I c and the corresponding value h (i, j) of matrix H are first converted into 8 bits binary sequence according to Eq. (5), respectively. Then, the bitwise exclusiveor (XOR) encryption is performed by using Eq. (7): Where x k e (i, j) represents encrypted binary of the k th bit and denotes XOR operation. Finally, the encrypted pixel x e (i, j) can be calculated according to Eq. (6). The encrypted image I e is obtained by the above process.

C. Data Hiding in Encrypted Image
In this subsection, to embed the additional data in the vacated room, the number of compressed bit-streams placed on the LSB plane is first extracted and the location of the vacated room can be obtained according to the extracted information. Then, the data hiding key K d is adopted to encrypt the additional data. Finally, the encrypted additional data is embedded into the vacated multi-LSB planes by LSB substitution. As shown in Fig. 9, the location of the vacated room generated in Fig. 8 can be obtained according to the number of compressed bit-streams. Then, the marked encrypted image I es is generated by LSB substitution.

D. Data Extraction and Image Recovery
The permission of data extraction and image recovery depend on the number of keys for the receiver. As shown in Fig. 10, there are three cases: Case 1: The receiver only has the key K d . Because the key K en only encrypts the image and does not affect the process of additional data, the extracted encrypted additional data can be correctly decrypted by key K d . However, the original image cannot be recovered without the key K en .
Case 2: The receiver only has the key K en . The original image can be restored. Firstly, the block of size, L f ix and the number of overflow pixel are extracted from MSB plane, and the number of compressed bit-streams for each bit-plane is extracted from LSB plane. Then, the image is decrypted by the key K en according to Eq. (7). The additional data cannot be extracted correctly without the key K d .
Case 3: The receiver has both the key K en and K d . The additional data can be extracted correctly and the original image can be recovered by the receiver.

IV. EXPERIMENTAL RESULTS AND DISCUSSION
In this section, the reversibility and the net embedding capacity of the proposed method is first analyzed in Section IV-A. Then, in order to demonstrate that the proposed method outperforms the state-of-the-art methods, such as [19], [21] [22], the experiments of embedding capacity is designed in Section IV-B. The peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) are used to evaluate the reversibility of the method. At the same time, the embedding rate (ER) is used as the evaluation index of the embedding capacity. As shown in Fig. 11, six standard gray images: Airplane, Lena, Man, Jetplane, Baboon and Tiffany and three datasets: UCID [24], BOSSbase [25] and BOWS-2 [26] are used. Next, the experimental results and discussion will be introduced in detail.
A. Performance Analysis of the Proposed Method 1) Discussion of Reversibility: To demonstrate the original image of the proposed method can be reconstructed lossless, as shown in Fig. 12, Lena is taken as an example. Fig. 12(a) is the original image I, and Fig. 12(b) is the encrypted image I e obtained by the encryption key K en . Fig. 12(c) shows the marked encrypted image I es that the ER is 3.0750 bpp. Since the data extraction and original image recovery can be separated in the proposed method, the content-owner can recover the original image using the encryption key K en . Fig. 12(d) is the reconstructed image. The PSNR of the reconstructed image close to +∞ and the SSIM equal to 1. That confirms the original image of the proposed method can be recovered lossless.
2) Discussion of Net Embedding Capacity: The proposed is performed to evaluate net ER in the test images and three databases [24]- [26], respectively. Table I shows the number of bit-streams of each bit-plane before and after compression for six test images. On the one hand, since the 8 th bit-plane is used to record the sign of the prediction error, the number of "0" and "1" is similar and is randomly distributed in the bitplane. Thus, the length of the compressed bit-streams is longer than that of the original bit-streams and the bit-plane is not compressed. On the other hand, because of the high accuracy of MED prediction, the number of "0" is far greater than "1" in the 7 th -5 th bit-planes and the length of the compressed bit-streams is less than that of the original bit-streams. Taken Airplane as an example, the length of compressed bit-streams is 5034 bits for the 7 th bit-plane. The compression degree is the largest compared with other bit-planes. The other five images have similar rules.
The length of auxiliary information, the net payload and ER are displayed in Table II on six test images. Assuming the number of overflow points is t for an image, its number and location used 18 bits and t × 18 bits to recorded, respectively. The block of size and the value of L f ix is denoted by 4 bits and  3 bits, respectively. The number of uncompressed bit-planes is recorded by s bits. It can be observed from Table II that the length of auxiliary information is far shorter than the vacated room on six test images. Taken Airplane as an example, its auxiliary information is recorded by 118 bits, the net payload is 1005663 bits and the net ER is 3.8363 bpp. Table III displays the average net ER of the proposed method on three databases [24]- [26]. For BOSSbase database, the net ER of the best case is 7.8305 bpp, and the net ER of the worst case is 0.7416 bpp.
For BOWS-2 database, the net ER of the best case is 7.0190 bpp, and the net ER of the worst case is 0.6239 bpp. But in UCID, the length of the auxiliary information of two images is longer than the vacated room. If these two images are not considered, the net ER of UCID the worst case is 0.2563 bpp.   6  17682  17933  90490  20816  143101  20277  5  28408  58371  346108  57296  240610  59735  4  71013  161631  974860  116385  -138435  3 182697

B. Performance Comparison
Since the proposed method and the state-of-the-art methods, such as [21] [22], all can reconstruct the original image lossless, the part only gives the performance comparison in terms of ER. Fig. 13 [26]. Since the MSB of the available pixels is substituted by 1 bit additional data in Puteaux et al. [19], the average ER is less than 1 bpp. Yin et al. [22] use the multi-MSB substitution to improve the average ER. In the UCID [24], the average ER of the proposed method is a significant  [25] and BOWS-2 [26].

V. CONCLUSIONS
In this paper, an RDHEI scheme based on pixel prediction and bit-plane compression is proposed. since the bit-planes of prediction error have a large number of adjacent "0" or "1", the characteristic is utilized to vacate more room. Experiments show that not only the image can be recovered and the embedded data can be extracted for the receiver, separately, but also the embedding capacity of the proposed method not only outperforms the state-of-the-art methods.
In future work, the embedding capacity will be enhanced in two ways. On the one hand, we inverse the part of the MSB and LSB and choose the shortest compression length. On the other hand, two different compression algorithms can be utilized for multi-MSB planes and multi-LSB planes. The proposed method can explore higher data embedding capacity.