# High-Capacity Reversible Data Hiding in Encrypted Images Based on Prediction Error Compression and Block Selection

Authors: Xu Wang; Li-Yao Li; Ching-Chun Chang; Chih-Cheng Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The popularity of cloud computing has impelled more users to upload personal data into the cloud server. The need for secure transmission and privacy protection has become a new challenge and has attracted considerable attention. In this paper, we propose a high-capacity reversible data hiding scheme in encrypted images (RDHEI) that compresses prediction errors in usable blocks of block-based encrypted images. On the content owner side, the original image is divided into2×2 sized blocks, and each block is encrypted by block-based modulation. On the data hider side, an efficient block-based predictor is utilized to generate prediction errors. The Huffman coding technique is introduced to compress prediction errors in the usable blocks to embed abundant additional data. On the receiver side, the additional data can be totally extracted with a data hiding key and the original image can be losslessly recovered with an image encryption key. Experimental results demonstrate that the embedding rate of our proposed scheme is significantly improved compared to those of state-of-the-art schemes.


---

## Body

## 1. Introduction

With the rapid development of 5G techniques and cloud services, users can easily download and upload data through high-speed communication networks and process data via cloud computing. Transmission security and privacy protection in the cloud have become severe challenges, especially in the digital image domain. Reversible data hiding and image encryption are two efficient techniques that can be adopted in this new environment. Reversible data hiding (RDH) can embed some sensitive messages into digital images and almost preserve the same image appearance so that the embedded data is imperceptible for unauthorized users [1]. Reversible data hiding techniques have been widely used in image retrieval, image forensics, and copyright watermarking, and some famous schemes have been proposed, such as difference expansion [2, 3], histogram shifting [4, 5], PVO (pixel value ordering) [6, 7], PEE (pixel error expansion) [8, 9], and even some deep learning schemes [10, 11]. Image encryption can encrypt the original meaningful plaintext image into a chaotic ciphertext image to protect the content [12]. An authorized user holds the encryption key that can completely recover the original image. In recent years, reversible data hiding in encrypted images (RDHEI) has drawn more and more attention and has been widely used in cloud applications. In such scenarios, the content owner encrypts an original image with an image encryption key and uploads the encrypted image into the cloud. The data hider downloads this encrypted image and embeds some additional data using a data hiding key. The receiver holds the data hiding key that can extract the embedded data, while the original image can be recovered with the image encryption key.Up to now, the reversible data hiding schemes in encrypted images can be classified into two categories: reserving the spare room before image encryption (RRBE) and vacating the spare room after image encryption (VRAE). In RRBE schemes, some preprocessing should be conducted on the original image before encryption on the content owner side. In [13], some conventional reversible data hiding techniques are directly adopted in the original image, to embed its own LSBs before encrypting; these LSBs can be totally replaced by additional data on the data hider side. Zhang et al. [14] estimated partial pixels before encryption so that the data hider could embed additional data into the estimating errors. In [15], each pixel’s MSB is predicted by its adjacent pixels, and data can be embedded into the MSBs with no prediction errors. More recently, a recursive scheme [16] has been proposed to process each bit plane. Image compression techniques have also been introduced in RRBE schemes. In [17], sparse coding and overcomplete dictionary techniques are used to compress the patch-level sparse matrices of the original image so that the remaining bits can carry the additional data. Extended run-length coding is applied in [18] to compress the original image bit planes. Some efficient compression techniques [19, 20] have been proposed to compress image bit planes to improve the embedding rate. Since the original meaningful image has certain textures, recent schemes explore redundancy in small regions. In these schemes, the original image is divided into blocks, and then bit plane compression [21], prediction error compression [21], and AMBTC compression [22] are adopted to compress each block. The complicated preprocessing in the RRBE schemes make them impractical in cloud applications, as they require too much processing capability for ordinary users.Unlike the RRBE schemes, in the VRAE schemes, the content owner only encrypts the original image and no preprocessing is needed. In the conventional VRAE schemes, bitwise encryption on each pixel is conducted such that no redundancy is preserved in the encrypted image. In [23], the encrypted image is first divided into blocks, and then an LSB flipping technique is used to embed data. The lowest smoothness level of the directly decrypted block and the flipped decrypted block is chosen for the final decrypted block and further determines the embedded bit. Since the image is fully encrypted, after data extraction and image recovery, errors exist in the extracted data and recovered image. Later, Hong et al. [24] utilized a side match smoothness algorithm to reduce the error rate. Deep learning technique is also introduced to improve the smoothness algorithm [25]. In these schemes, the processes of image recovery and data extraction are joined. The separable scheme is proposed in [26] and has become a common approach. To increase the embedding rate or reduce the error rate, some related schemes [27–29] have been proposed. To eliminate errors, some specific image encryption methods have been proposed that preserve some relevance, such as homomorphic encryption [30–32], half-pixel value encryption [33], and block-based encryption [34–39]. Since some relevance in each block can be preserved in block-based encryption, schemes using these encryption methods have matured in recent years. Huang et al. [34] encrypted all pixels in one block with the same 8-bit key through bitwise exclusive OR and then used RDH techniques such as histogram shifting and prediction error shifting to embed data. More recently, a multilevel approach to improve the performance is proposed in [35]. In [36], pixel MSBs in a block are classified into different types and compressed to vacate the room for data embedding. Exploring redundancy in the bit plane for each block has also performed well. In [37, 38], each bit plane in a block is compressed. In [39], each block is adaptively encoded by Huffman coding according to how many bit planes have the same binary value.These block-based VRAE schemes usually set a larger block size, for example,4×4, to achieve better embedding rates. However, such block size will lead to an obvious block effect in the encrypted image. Meanwhile, the encryption key space is also insufficient in these schemes. To improve security, some schemes have been proposed in recent years to optimize performance in smaller block sizes such as 2×2. In [40], the run-length coding compression technique is introduced to compress three-pixel differences in each embeddable block. Wang et al. [41] saved three-pixel differences and the index of the next embeddable block so that the remaining bits in the current embeddable block can be vacated. The binary bit-level difference in each embeddable block is also considered and compressed in [42]. The pixel differences in [43] are simply compressed using the Huffman coding technique. Unfortunately, redundancy is underutilized in these small block size schemes.The main purpose of this paper is to further improve the embedding rate to achieve the best performance compared to the above schemes when the block size is2×2 in cloud cryptoimage privacy protection applications. In this paper, we compress the prediction errors instead of the pixel differences. Therefore, block-based modulation is introduced to encrypt the image, and an efficient predictor is applied in each block to obtain prediction errors with a more centralized distribution. Then, the Huffman coding technique is used to encode each prediction error and obtain corresponding indicators. The shorter indicators can represent most prediction errors, so the encrypted image can be efficiently compressed. Additionally, according to the final length of the encoded sequence, all blocks can be classified into usable blocks and unusable blocks. Then, prediction errors in the usable blocks are encoded by indicators and preserve the initial pixels in unusable blocks. Therefore, after compressing and encoding on the data hider side, abundant additional bits can be embedded into the encrypted image. When receiving the embedded encrypted image, a recipient can extract the embedded bits with the data hiding key and recover the original image with the image encryption key. The main contributions of our proposed scheme are as follows:(1)
Prediction errors are compressed, instead of pixel differences or binary bit-level differences(2)
An efficient block-based predictor is utilized with blocks encrypted by block-based modulation to obtain more centralized prediction errors(3)
The Huffman coding technique is used to generate indicators so that each prediction error in the usable blocks can be encoded by corresponding indicators(4)
The embedding rate can be improved by 0.4929 bpp compared to other state-of-the-art schemesThe rest of this paper is organized as follows: Section2 describes the proposed scheme in detail, including image encryption, pixel prediction, prediction error compression, block selection, data embedding, data extraction, and image recovery. Section 3 provides some experimental results and comparisons. The conclusions are offered in Section 4.


## 2. Proposed Scheme

In this section, we introduce the detailed RDHEI scheme that compresses prediction errors in the selected blocks to create abundant room for data embedding. Figure1 illustrates the framework of our proposed scheme. In image encryption, each block is encrypted by pixel modulation to preserve the correlations among pixels as much as possible. Four different prediction directions are applied to the encrypted blocks on the data hider side to further narrow the range of prediction errors. Then, all blocks are classified into usable blocks and unusable blocks, and the Huffman coding technique is adopted to encode each prediction error in the usable blocks and keep the initial encrypted pixels unchanged in the unusable blocks. On the receiver side, the embedded data can be totally extracted with a data hiding key, and the original image can be recovered with an image encryption key. Image encryption, pixel prediction, prediction error compression, block selection, data embedding, data extraction, and image recovery are detailed in the following.Figure 1
Framework of our proposed scheme.


### 2.1. Image Encryption

To better preserve the correlation among pixels in each block, block-based modulation is used to encrypt the image. Before encrypting, theM×M sized original image O is first divided into nonoverlapping blocks. To ensure security, this paper chooses the smallest block size, that is, 2×2, to decompose the image into M2/4 blocks. Then, the block-based modulation key Km is generated, containing M2/4 random decimal integer subkeys from 0 to 255. Taking the 512×512 test images, there are 65,536 image blocks so that the block-based modulation key has 65,536 random decimal integers. For each block, all pixels are encrypted by the same subkey using(1)ecs=ocs+Kmsmod256,where o and e represent the original pixel and the encrypted pixel, respectively, while s and h denote the block index and pixel index in the s-th block, respectively. After encrypting, in most blocks, all pixels are increased or decreased by the same degree, which is instrumental in prediction. The original pixels can be completely recovered by equation (2). Two simple examples are given in Figure 2 to illustrate the differences between block-based modulation and exclusive OR. It is obvious that the block-based modulation method can preserve pixel differences, while exclusive OR enlarges them. Therefore, the block-based modulation is more suitable for this paper.Figure 2
Examples of two encryption methods.(2)ocs=ecs−Kmsmod256.To further enhance security, all encrypted blocks are permuted following a permutation keyKp that contains M2/4 random and nonrepetitive integers to disrupt the correlation among blocks and obtain the final encrypted image E.


### 2.2. Pixel Prediction

When receiving the encrypted imageE, an efficient block-based predictor serves to obtain prediction errors for each block on the data hider side. Denoting four pixels e in an encrypted block as e1, e2, e3, and e4, following the raster scan order, we keep e1 unchanged as a reference pixel and use equations (3)–(5) to obtain three prediction pixels p:p2,p3,p4.(3)p2=e2−e1,(4)p3=e3−e1,(5)p4=mine2,e3,ife1≥maxe2,e3,maxe2,e3,ife1≤mine2,e3,e2+e3−e1,otherwise,where p represents the prediction pixel. Since the encrypted block still has certain texture directionalities, different prediction directions will affect the accuracy of the prediction. Similar to equations (3)–(5), the encrypted pixels e2 to e4 in each block are sequentially chosen as reference pixels to predict the remaining three pixels. As shown in Figure 3, different prediction directions can lead to different prediction errors. The grey pixels in four blocks are reference pixels. The vertical and horizon prediction errors can be directly calculated by reference pixels through equations (3) and (4). For the diagonal pixel, the reference pixel can be denoted as e1 and the vertical and horizon pixels are e2 and e3, so that the prediction error can be obtained by equation (5). Therefore, four prediction directions are utilized in the whole encrypted image to fit different texture images, and we choose the most accurate prediction direction as the final predictor. As to cost, only two bits are used to record four prediction directions, and they can be regarded as one part of the data hiding key. After obtaining the prediction pixels, the prediction errors pe can be calculated by(6)pe=e−p.Figure 3
Examples of four prediction directions.Therefore, the proposed block-based predictor with four prediction directions can effectively narrow the range of prediction errors, which is of great benefit to prediction error compression in the next section.


### 2.3. Prediction Error Compression and Block Selection

After processing each encrypted block with our proposed predictor, all prediction errors in the range [−255, 255] can be obtained. Since the image encryption method preserves relevance in the block and the proposed predictor has higher accuracy, most prediction errors are centralized in a small range. For instance, in the test image “Lena,” 87% (171,245/196,608) of prediction errors are in the range [−10, 10]. Therefore, the generated prediction errors can be effectively compressed. Inspired by [43], we also use the Huffman coding technique to compress prediction errors. The detailed encoding and compression procedures are as follows:Step 1. Import all prediction errors.Step 2. Count the number of different prediction error values, from −255 to 255.Step 3. Feed these numbers into the Huffman coding compression to generate the Huffman coding map H, which contains 511 indicators for each prediction error.Step 4. Use the corresponding indicators to encode three prediction errors in each block following the raster scan order until all blocks have been encoded. The final encoded sequence S of the encrypted image can be obtained by gathering all encoded blocks.After encoding, each prediction error can be represented by different lengths of indicators, and the most frequent prediction error has the shortest indicator, so these prediction errors can be encoded using shorter indicators to achieve compression. We can simply look up the Huffman coding mapH, as shown in Table 1, to recover each prediction error according to the indicator. In the Huffman coding map H, for each prediction error, we only record the length of the indicator and the corresponding binary indicator bits. The length of the indicator can be represented by log2maxLength bits, whererepresents the ceiling function and maxLength denotes the length of the longest indicator.Table 1
The Huffman coding map of “Lena.”
Prediction errorLengthIndicator−255120110 0001 0011−254110110 0001 100−253110010 0000 111………−14000103101140000………253101111 1011 00254110010 0010 101255120010 0010 1111In the encoded sequenceS, the length is shorter than 24 bits (the initial length of three predictable pixels in one block) in some smooth blocks, because the prediction errors are small to achieve compression. However, in some complex blocks, the length of the encoded sequence may exceed 24 bits, and these blocks are not profitable for compression. Therefore, for each block in our scheme, if the length of the encoded sequence is less than or equal to 24 bits, it can be classified as a usable block (UB) and the encoded sequence is kept unchanged. Conversely, if the length of the encoded sequence of one block is greater than 24 bits, it is classified as an unusable block (NUB); then, the encoded sequence is replaced by the initial 24 bits of three encrypted pixels. Figure 4 gives some examples to illustrate block selection. Consequently, a location map L, with a length equal to the number of blocks, is used to record blocks that are usable as “1” and blocks are unusable as “0.” The location map is a sparse matrix because the meaningful image still has block smoothness after encrypting with our proposed image encryption; thus, the location map L can be further compressed using arithmetic coding to obtain the shorter compressed location map L′. The final encoded sequence S and the compressed location map L′ contain all initial encrypted image content, which can be used to completely recover the encrypted image E.Figure 4
An example of block selection.


### 2.4. Data Embedding

Since the first pixel in each block is preserved as the reference pixel, the bits of the remaining three pixels can be completely vacated for data embedding. On the receiver side, after compressing the prediction errors, the Huffman coding mapH, the compressed location map L′, and the encoded sequence S should be embedded into the vacated room to recover the encrypted image. We denote these data as auxiliary information and embed them from the third embeddable pixel and then use the first two embeddable pixels to record the ending coordinate. After the auxiliary information has been embedded, the rest of the vacated room can be used for additional data embedding. The to-be-embedded additional data A is first encrypted by a data hiding key Kh to obtain the encrypted additional data A′. The generated data hiding key contains random binary bits and has the same length as the additional data. The bitwise exclusive OR operation is applied to encrypt A. Then, A′ is embedded behind the auxiliary information. If all A′ has been embedded and there is still some vacated room, random bits are generated to fill up this space, and the final embedded encrypted image E′ is obtained.


### 2.5. Data Extraction and Image Recovery

From the embedded encrypted imageE′, the embedded additional data A can be totally extracted using the data hiding key Kh, and the original image O can be completely recovered using the image encryption keys Km and Kp on the receiver side. The detailed procedures are described as follows.


#### 2.5.1. Data Extraction

After receiving the embedded encrypted imageE′, the receiver also needs to divide it into nonoverlapping 2×2 sized blocks. Since the first encrypted pixel of each block is the reference pixel, the following two pixels indicate the ending coordinate of the auxiliary information. Therefore, all bits behind the ending coordinate are encrypted embedded additional data A′, which can be extracted. Then, the data hiding key Kh is used to decrypt A′ to obtain the additional data A.


#### 2.5.2. Image Recovery

If the receiver has the image encryption keysKm and Kp, the original image can be completely recovered without any loss. The auxiliary information which contains the Huffman coding map H, the compressed location map L′, and the encoded sequence S should be extracted first. The detailed image recovery procedures are as follows:Step 1. Adopt arithmetic coding technique to decompress L′ to obtain the location map L with the length of M2/4.Step 2. If the bit in the location map L′ is “0,” the block is unusable; go to Step 3. Otherwise, the block is usable; go to Step 4.Step 3: Extract 24 bits from the encoded sequence S to recover three initial pixels and go to Step 7.Step 4: Look up the Huffman coding map H to recover corresponding bits in the encoded sequence S to obtain three prediction errors in a usable block.Step 5. Use equations (3) and (4) to obtain two prediction pixels according to the corresponding reference pixel, and recover two initial encrypted pixels e using(7)e=pe+p.Step 6. Use equation (5) and three adjacent pixels to obtain the diagonal prediction pixel of the reference pixel, and recover the initial encrypted pixels using equation (7)Step 7. Rearrange each block using the block permutation key Kp; then, according to the block-based modulation key Km, decrypt all pixels of one block using equation (2) to recover the original pixels.After processing all blocks by the above steps, the original imageO can be completely recovered without any loss.


## 2.1. Image Encryption

To better preserve the correlation among pixels in each block, block-based modulation is used to encrypt the image. Before encrypting, theM×M sized original image O is first divided into nonoverlapping blocks. To ensure security, this paper chooses the smallest block size, that is, 2×2, to decompose the image into M2/4 blocks. Then, the block-based modulation key Km is generated, containing M2/4 random decimal integer subkeys from 0 to 255. Taking the 512×512 test images, there are 65,536 image blocks so that the block-based modulation key has 65,536 random decimal integers. For each block, all pixels are encrypted by the same subkey using(1)ecs=ocs+Kmsmod256,where o and e represent the original pixel and the encrypted pixel, respectively, while s and h denote the block index and pixel index in the s-th block, respectively. After encrypting, in most blocks, all pixels are increased or decreased by the same degree, which is instrumental in prediction. The original pixels can be completely recovered by equation (2). Two simple examples are given in Figure 2 to illustrate the differences between block-based modulation and exclusive OR. It is obvious that the block-based modulation method can preserve pixel differences, while exclusive OR enlarges them. Therefore, the block-based modulation is more suitable for this paper.Figure 2
Examples of two encryption methods.(2)ocs=ecs−Kmsmod256.To further enhance security, all encrypted blocks are permuted following a permutation keyKp that contains M2/4 random and nonrepetitive integers to disrupt the correlation among blocks and obtain the final encrypted image E.


## 2.2. Pixel Prediction

When receiving the encrypted imageE, an efficient block-based predictor serves to obtain prediction errors for each block on the data hider side. Denoting four pixels e in an encrypted block as e1, e2, e3, and e4, following the raster scan order, we keep e1 unchanged as a reference pixel and use equations (3)–(5) to obtain three prediction pixels p:p2,p3,p4.(3)p2=e2−e1,(4)p3=e3−e1,(5)p4=mine2,e3,ife1≥maxe2,e3,maxe2,e3,ife1≤mine2,e3,e2+e3−e1,otherwise,where p represents the prediction pixel. Since the encrypted block still has certain texture directionalities, different prediction directions will affect the accuracy of the prediction. Similar to equations (3)–(5), the encrypted pixels e2 to e4 in each block are sequentially chosen as reference pixels to predict the remaining three pixels. As shown in Figure 3, different prediction directions can lead to different prediction errors. The grey pixels in four blocks are reference pixels. The vertical and horizon prediction errors can be directly calculated by reference pixels through equations (3) and (4). For the diagonal pixel, the reference pixel can be denoted as e1 and the vertical and horizon pixels are e2 and e3, so that the prediction error can be obtained by equation (5). Therefore, four prediction directions are utilized in the whole encrypted image to fit different texture images, and we choose the most accurate prediction direction as the final predictor. As to cost, only two bits are used to record four prediction directions, and they can be regarded as one part of the data hiding key. After obtaining the prediction pixels, the prediction errors pe can be calculated by(6)pe=e−p.Figure 3
Examples of four prediction directions.Therefore, the proposed block-based predictor with four prediction directions can effectively narrow the range of prediction errors, which is of great benefit to prediction error compression in the next section.


## 2.3. Prediction Error Compression and Block Selection

After processing each encrypted block with our proposed predictor, all prediction errors in the range [−255, 255] can be obtained. Since the image encryption method preserves relevance in the block and the proposed predictor has higher accuracy, most prediction errors are centralized in a small range. For instance, in the test image “Lena,” 87% (171,245/196,608) of prediction errors are in the range [−10, 10]. Therefore, the generated prediction errors can be effectively compressed. Inspired by [43], we also use the Huffman coding technique to compress prediction errors. The detailed encoding and compression procedures are as follows:Step 1. Import all prediction errors.Step 2. Count the number of different prediction error values, from −255 to 255.Step 3. Feed these numbers into the Huffman coding compression to generate the Huffman coding map H, which contains 511 indicators for each prediction error.Step 4. Use the corresponding indicators to encode three prediction errors in each block following the raster scan order until all blocks have been encoded. The final encoded sequence S of the encrypted image can be obtained by gathering all encoded blocks.After encoding, each prediction error can be represented by different lengths of indicators, and the most frequent prediction error has the shortest indicator, so these prediction errors can be encoded using shorter indicators to achieve compression. We can simply look up the Huffman coding mapH, as shown in Table 1, to recover each prediction error according to the indicator. In the Huffman coding map H, for each prediction error, we only record the length of the indicator and the corresponding binary indicator bits. The length of the indicator can be represented by log2maxLength bits, whererepresents the ceiling function and maxLength denotes the length of the longest indicator.Table 1
The Huffman coding map of “Lena.”
Prediction errorLengthIndicator−255120110 0001 0011−254110110 0001 100−253110010 0000 111………−14000103101140000………253101111 1011 00254110010 0010 101255120010 0010 1111In the encoded sequenceS, the length is shorter than 24 bits (the initial length of three predictable pixels in one block) in some smooth blocks, because the prediction errors are small to achieve compression. However, in some complex blocks, the length of the encoded sequence may exceed 24 bits, and these blocks are not profitable for compression. Therefore, for each block in our scheme, if the length of the encoded sequence is less than or equal to 24 bits, it can be classified as a usable block (UB) and the encoded sequence is kept unchanged. Conversely, if the length of the encoded sequence of one block is greater than 24 bits, it is classified as an unusable block (NUB); then, the encoded sequence is replaced by the initial 24 bits of three encrypted pixels. Figure 4 gives some examples to illustrate block selection. Consequently, a location map L, with a length equal to the number of blocks, is used to record blocks that are usable as “1” and blocks are unusable as “0.” The location map is a sparse matrix because the meaningful image still has block smoothness after encrypting with our proposed image encryption; thus, the location map L can be further compressed using arithmetic coding to obtain the shorter compressed location map L′. The final encoded sequence S and the compressed location map L′ contain all initial encrypted image content, which can be used to completely recover the encrypted image E.Figure 4
An example of block selection.


## 2.4. Data Embedding

Since the first pixel in each block is preserved as the reference pixel, the bits of the remaining three pixels can be completely vacated for data embedding. On the receiver side, after compressing the prediction errors, the Huffman coding mapH, the compressed location map L′, and the encoded sequence S should be embedded into the vacated room to recover the encrypted image. We denote these data as auxiliary information and embed them from the third embeddable pixel and then use the first two embeddable pixels to record the ending coordinate. After the auxiliary information has been embedded, the rest of the vacated room can be used for additional data embedding. The to-be-embedded additional data A is first encrypted by a data hiding key Kh to obtain the encrypted additional data A′. The generated data hiding key contains random binary bits and has the same length as the additional data. The bitwise exclusive OR operation is applied to encrypt A. Then, A′ is embedded behind the auxiliary information. If all A′ has been embedded and there is still some vacated room, random bits are generated to fill up this space, and the final embedded encrypted image E′ is obtained.


## 2.5. Data Extraction and Image Recovery

From the embedded encrypted imageE′, the embedded additional data A can be totally extracted using the data hiding key Kh, and the original image O can be completely recovered using the image encryption keys Km and Kp on the receiver side. The detailed procedures are described as follows.


### 2.5.1. Data Extraction

After receiving the embedded encrypted imageE′, the receiver also needs to divide it into nonoverlapping 2×2 sized blocks. Since the first encrypted pixel of each block is the reference pixel, the following two pixels indicate the ending coordinate of the auxiliary information. Therefore, all bits behind the ending coordinate are encrypted embedded additional data A′, which can be extracted. Then, the data hiding key Kh is used to decrypt A′ to obtain the additional data A.


### 2.5.2. Image Recovery

If the receiver has the image encryption keysKm and Kp, the original image can be completely recovered without any loss. The auxiliary information which contains the Huffman coding map H, the compressed location map L′, and the encoded sequence S should be extracted first. The detailed image recovery procedures are as follows:Step 1. Adopt arithmetic coding technique to decompress L′ to obtain the location map L with the length of M2/4.Step 2. If the bit in the location map L′ is “0,” the block is unusable; go to Step 3. Otherwise, the block is usable; go to Step 4.Step 3: Extract 24 bits from the encoded sequence S to recover three initial pixels and go to Step 7.Step 4: Look up the Huffman coding map H to recover corresponding bits in the encoded sequence S to obtain three prediction errors in a usable block.Step 5. Use equations (3) and (4) to obtain two prediction pixels according to the corresponding reference pixel, and recover two initial encrypted pixels e using(7)e=pe+p.Step 6. Use equation (5) and three adjacent pixels to obtain the diagonal prediction pixel of the reference pixel, and recover the initial encrypted pixels using equation (7)Step 7. Rearrange each block using the block permutation key Kp; then, according to the block-based modulation key Km, decrypt all pixels of one block using equation (2) to recover the original pixels.After processing all blocks by the above steps, the original imageO can be completely recovered without any loss.


## 2.5.1. Data Extraction

After receiving the embedded encrypted imageE′, the receiver also needs to divide it into nonoverlapping 2×2 sized blocks. Since the first encrypted pixel of each block is the reference pixel, the following two pixels indicate the ending coordinate of the auxiliary information. Therefore, all bits behind the ending coordinate are encrypted embedded additional data A′, which can be extracted. Then, the data hiding key Kh is used to decrypt A′ to obtain the additional data A.


## 2.5.2. Image Recovery

If the receiver has the image encryption keysKm and Kp, the original image can be completely recovered without any loss. The auxiliary information which contains the Huffman coding map H, the compressed location map L′, and the encoded sequence S should be extracted first. The detailed image recovery procedures are as follows:Step 1. Adopt arithmetic coding technique to decompress L′ to obtain the location map L with the length of M2/4.Step 2. If the bit in the location map L′ is “0,” the block is unusable; go to Step 3. Otherwise, the block is usable; go to Step 4.Step 3: Extract 24 bits from the encoded sequence S to recover three initial pixels and go to Step 7.Step 4: Look up the Huffman coding map H to recover corresponding bits in the encoded sequence S to obtain three prediction errors in a usable block.Step 5. Use equations (3) and (4) to obtain two prediction pixels according to the corresponding reference pixel, and recover two initial encrypted pixels e using(7)e=pe+p.Step 6. Use equation (5) and three adjacent pixels to obtain the diagonal prediction pixel of the reference pixel, and recover the initial encrypted pixels using equation (7)Step 7. Rearrange each block using the block permutation key Kp; then, according to the block-based modulation key Km, decrypt all pixels of one block using equation (2) to recover the original pixels.After processing all blocks by the above steps, the original imageO can be completely recovered without any loss.


## 3. Experimental Results

In this section, several experiments are conducted to evaluate our proposed scheme and compare it with other state-of-the-art schemes. The experiments are mainly based on eight test images: “Airplane,” “Baboon,” “Barbara,” “Boat,” “Elaine,” “House,” “Lena,” and “Peppers” shown in Figure5; each of them has 512×512 grayscale pixels. The famous image dataset BOSSBase [44] is also introduced to verify the adaptability of our proposed scheme.Figure 5
Eight test images. (a) Airplane. (b) Baboon. (c) Barbara. (d) Boat. (e) Elaine. (f) House. (g) Lena. (h) Peppers.
(a)(b)(c)(d)(e)(f)(g)(h)We use two important metrics, PSNR (dB) and embedding rate (bpp), to evaluate performance. PSNR (peak signal-to-noise ratio) estimates the difference in visual quality between the decrypted image and the original image, which can be calculated by equations (8) and (9). The embedding rate is the average number of bits that can be embedded per pixel and can be obtained by equation (10), where the symbol A denotes the length of A. In Section 3.1, we evaluate the prediction accuracy of the proposed predictor. Then, the performance and security analysis of our proposed scheme are provided in Section 3.2. The embedding rate comparisons of our proposed scheme and state-of-the-art schemes are given in Section 3.3.(8)MSE=1M×N∑i=1M∑j=1NOi,j−Di,j2,(9)PSNR=10log102552MSEdB,(10)γ=AM×Nbpp.


### 3.1. Accuracy of Our Proposed Predictor

Since the accuracy of the predictor will affect the distribution of the prediction errors, a more accurate predictor can reduce the length of the encoded sequence and increase the embedding rate because of the characteristics of the Huffman coding technique. Therefore, we first evaluate the proposed predictor with the pixel difference technique from [43]. In Table 2, the sums of the absolute prediction errors of different cases are listed; a lower value indicates that the predictor has higher prediction accuracy. The third column denotes that the image encryption method is replaced by our method described in Section 2.1. The symbol d denotes four prediction directions. It is obvious that the image encryption technique used in this paper is more suitable for prediction. The proposed predictor can further increase prediction accuracy. Additionally, two examples of prediction error distributions in different cases are presented in Figure 6. The result of our proposed scheme is obtained by the best prediction direction of each image. It can be seen that the distributions of our proposed scheme in two images are centralized so that more prediction errors can be compressed and encoded by Huffman coding with shorter indicator bits. Therefore, our proposed predictor has higher prediction accuracy than the pixel difference in the conventional schemes.Table 2
The sum of the absolute prediction errors in different cases.
Images[43][43]′d=1d=2d=3d=4Airplane296294522815211888283190054918969951904834Baboon784417460781385628995560721456043665606141Barbara530553242329443805040382478338201853824680Boat423097732304612834319284797428383492840883Elaine429209228099342795220280774828041892808269House404212229695322411995241580524080562413886Lena340632822636581973217200147819923051977164Peppers331872924615232374853237330123808772366888Figure 6
Prediction error distributions for the test images: (a) “Airplane” and (b) “Lena.”
(a)(b)


### 3.2. Performance and Security Analysis

In Figure7, the image results generated in different phases of our proposed scheme are first given by using two test images, “Lena” and “Peppers.” It can be observed that the contents of the encrypted images and embedded encrypted images are all chaotic, and no useful information is revealed from the histograms. Meanwhile, the experiment results certified that the original image can be totally recovered.Figure 7
Images of the test images “Lena” and “Peppers”: (a) original images, (b) encrypted images, (c) embedded encrypted images, and (d) recovered images. Images in the second row and fourth row are the corresponding pixel value histograms.The complexity of the image will no doubt affect the accuracy of the prediction so that the number of usable and unusable blocks is different in the test images. Therefore, the number of different block types, the length of the compressed location mapL′, and the embedded rates of test images are listed in Table 1 to illustrate the performance of our proposed scheme. In Table 3, γ′ denotes the embedding rate without block selection. There are indeed several blocks unsuitable for prediction error compression. The block types can be recorded using a short location map length, and the embedding rate can be efficiently improved. Additionally, the best prediction direction in each image is different, so we use d to denote which pixel is the reference for prediction error generation following the raster scan order. Besides these eight test images, we also evaluate the embedding rate of our proposed scheme on the famous dataset BOSSBase. The embedding rates of the worst case, best case, and average are listed in Table 4. Even the most complex image can achieve a 0.6317 bpp embedding rate. Meanwhile, the cumulative distribution curve of the dataset is shown in Figure 8. Almost 75% of the embedding rates are concentrated between 2 bpp and 4 bpp, showing that, for most images, the spare room is more than sufficient to embed additional data. To sum up, our proposed scheme has good adaptability to different images.Table 3
Performance of our proposed scheme in different images.
Images|UBs||NUBs|L′γ′γdPSNRAirplane60991454568332.45762.55601InfBaboon5348512051192500.87251.02313InfBarbara5501210524165881.49091.65883InfBoat60479505776301.80581.90561InfElaine61809372755731.79861.87932InfHouse60229530780222.11292.20434InfLena61594372455692.26222.35161InfPeppers61594394259032.05752.14691InfTable 4
Embedding rate and PSNR of different cases.
FactorsWorst caseBest caseAverageγ0.63175.16882.8303PSNRInfInfInfFigure 8
Cumulative distribution curve of the embedding rate in BOSSBase.Since our proposed scheme is utilized in the encryption domain, we further conduct a quantified security analysis to evaluate it. Table5 lists the PSNR, NPCR, and Entropy of the encrypted images and embedded encrypted images. PSNR and NPCR denote the difference between an encrypted or embedded encrypted image and the original image. The result verifies that the pixels in the encrypted image and embedded encrypted image are far different from the original pixels. Two average Entropy values are all close to 8, which indicates that the histograms of the encrypted image and embedded encrypted image are flat enough that no statistical features can be detected.Table 5
Quantified security analysis of encrypted images and embedded encrypted images.
ImagesPSNRNPCREntropyEncrypted imageEmbedded imageEncrypted imageEmbedded imageEncrypted imageEmbedded imageAirplane8.03778.08220.99610.99607.99897.9970Baboon9.53269.55140.99610.99607.99917.9970Barbara8.84408.83900.99610.99627.99927.9969Boat9.30609.32960.99590.99597.99927.9971Elaine9.31759.32340.99630.99597.99907.9968House8.69838.73830.99600.99617.99927.9967Lena9.26469.25400.99590.99587.99917.9972Peppers8.90988.90970.99600.99617.99917.9969Average8.98889.00350.99610.99607.99917.9970


### 3.3. Comparison

Since most block-based VRAE schemes can completely recover the original image, in this section, we conduct embedding rate comparisons to demonstrate the advantages of our proposed scheme as compared to some state-of-the-art schemes. In each compared scheme, we simulate the optimal parameters to achieve the best embedding rate. For our proposed scheme, we adaptively choose the prediction direction for each image. We first compare the embedding rates among our scheme and eight related schemes [34–36, 39–43] for eight test images. In Table 6, the embedding rates of [34, 35] are relatively low, because the conventional reversible data hiding techniques of the spatial domain have been adopted. Schemes [36, 40–42] improve the embedding rate by vacating the spare room in each block’s bit plane. Scheme [39] adaptively compresses bit planes, so the embedding rate provided by this scheme is higher than the above bit plane schemes. Scheme [43] turns to compress the pixel differences; however, the spare room is not fully utilized. Since our scheme compresses the prediction errors and improves the prediction direction and block selection, it has the highest embedding rates for all eight images. Additionally, our proposed scheme has a noticeable improvement, that is, achieves 0.4994 bpp more than the second-highest ranked scheme [39]. Obviously, our scheme is superior to other state-of-the-art schemes, such that abundant additional secret data can be embedded into encrypted images.Table 6
Maximum embedding rate comparison in eight test images.
ImagesHuang et al. [34]Ge et al. [35]Qin et al. [40]Fu et al. [36]Wang et al. [41]Liu and Pun [42]Chen [43]Wang et al. [39]Proposed schemeAirplane0.14650.24230.77901.21221.15811.47531.68712.05202.5560Baboon0.02220.01320.22220.15700.22820.46460.31330.63221.0231Barbara0.06480.07820.38610.67710.62870.88160.86381.23491.6588Boat0.05570.06510.31490.65170.75261.11221.06861.41811.9056Elaine0.05380.06600.33210.58110.79041.05391.06761.32471.8793House0.14390.21430.82520.95150.82311.13271.32341.69732.2043Lena0.09480.13880.52311.02180.87491.35431.42201.74142.3516Peppers0.06190.08870.35610.87650.81761.23491.34361.62962.1469Average0.08050.11330.46730.76610.75921.08871.13611.46631.9657To further evaluate adaptability, we also compare the embedding rates on the BOSSBase dataset among our scheme and the six state-of-the-art schemes [36, 39–43] with higher embedding rates. As shown in Figure 9, the embedding rates in the first three schemes are relatively low. Only in our scheme and [39], embedding rates exceed 2 bpp, and our scheme has an improvement of 0.4929 bpp over [39]. Consequently, our proposed scheme is significantly superior to the state-of-the-art schemes and is applicable to a variety of images.Figure 9
Embedding rate comparison in BOSSBase.


## 3.1. Accuracy of Our Proposed Predictor

Since the accuracy of the predictor will affect the distribution of the prediction errors, a more accurate predictor can reduce the length of the encoded sequence and increase the embedding rate because of the characteristics of the Huffman coding technique. Therefore, we first evaluate the proposed predictor with the pixel difference technique from [43]. In Table 2, the sums of the absolute prediction errors of different cases are listed; a lower value indicates that the predictor has higher prediction accuracy. The third column denotes that the image encryption method is replaced by our method described in Section 2.1. The symbol d denotes four prediction directions. It is obvious that the image encryption technique used in this paper is more suitable for prediction. The proposed predictor can further increase prediction accuracy. Additionally, two examples of prediction error distributions in different cases are presented in Figure 6. The result of our proposed scheme is obtained by the best prediction direction of each image. It can be seen that the distributions of our proposed scheme in two images are centralized so that more prediction errors can be compressed and encoded by Huffman coding with shorter indicator bits. Therefore, our proposed predictor has higher prediction accuracy than the pixel difference in the conventional schemes.Table 2
The sum of the absolute prediction errors in different cases.
Images[43][43]′d=1d=2d=3d=4Airplane296294522815211888283190054918969951904834Baboon784417460781385628995560721456043665606141Barbara530553242329443805040382478338201853824680Boat423097732304612834319284797428383492840883Elaine429209228099342795220280774828041892808269House404212229695322411995241580524080562413886Lena340632822636581973217200147819923051977164Peppers331872924615232374853237330123808772366888Figure 6
Prediction error distributions for the test images: (a) “Airplane” and (b) “Lena.”
(a)(b)


## 3.2. Performance and Security Analysis

In Figure7, the image results generated in different phases of our proposed scheme are first given by using two test images, “Lena” and “Peppers.” It can be observed that the contents of the encrypted images and embedded encrypted images are all chaotic, and no useful information is revealed from the histograms. Meanwhile, the experiment results certified that the original image can be totally recovered.Figure 7
Images of the test images “Lena” and “Peppers”: (a) original images, (b) encrypted images, (c) embedded encrypted images, and (d) recovered images. Images in the second row and fourth row are the corresponding pixel value histograms.The complexity of the image will no doubt affect the accuracy of the prediction so that the number of usable and unusable blocks is different in the test images. Therefore, the number of different block types, the length of the compressed location mapL′, and the embedded rates of test images are listed in Table 1 to illustrate the performance of our proposed scheme. In Table 3, γ′ denotes the embedding rate without block selection. There are indeed several blocks unsuitable for prediction error compression. The block types can be recorded using a short location map length, and the embedding rate can be efficiently improved. Additionally, the best prediction direction in each image is different, so we use d to denote which pixel is the reference for prediction error generation following the raster scan order. Besides these eight test images, we also evaluate the embedding rate of our proposed scheme on the famous dataset BOSSBase. The embedding rates of the worst case, best case, and average are listed in Table 4. Even the most complex image can achieve a 0.6317 bpp embedding rate. Meanwhile, the cumulative distribution curve of the dataset is shown in Figure 8. Almost 75% of the embedding rates are concentrated between 2 bpp and 4 bpp, showing that, for most images, the spare room is more than sufficient to embed additional data. To sum up, our proposed scheme has good adaptability to different images.Table 3
Performance of our proposed scheme in different images.
Images|UBs||NUBs|L′γ′γdPSNRAirplane60991454568332.45762.55601InfBaboon5348512051192500.87251.02313InfBarbara5501210524165881.49091.65883InfBoat60479505776301.80581.90561InfElaine61809372755731.79861.87932InfHouse60229530780222.11292.20434InfLena61594372455692.26222.35161InfPeppers61594394259032.05752.14691InfTable 4
Embedding rate and PSNR of different cases.
FactorsWorst caseBest caseAverageγ0.63175.16882.8303PSNRInfInfInfFigure 8
Cumulative distribution curve of the embedding rate in BOSSBase.Since our proposed scheme is utilized in the encryption domain, we further conduct a quantified security analysis to evaluate it. Table5 lists the PSNR, NPCR, and Entropy of the encrypted images and embedded encrypted images. PSNR and NPCR denote the difference between an encrypted or embedded encrypted image and the original image. The result verifies that the pixels in the encrypted image and embedded encrypted image are far different from the original pixels. Two average Entropy values are all close to 8, which indicates that the histograms of the encrypted image and embedded encrypted image are flat enough that no statistical features can be detected.Table 5
Quantified security analysis of encrypted images and embedded encrypted images.
ImagesPSNRNPCREntropyEncrypted imageEmbedded imageEncrypted imageEmbedded imageEncrypted imageEmbedded imageAirplane8.03778.08220.99610.99607.99897.9970Baboon9.53269.55140.99610.99607.99917.9970Barbara8.84408.83900.99610.99627.99927.9969Boat9.30609.32960.99590.99597.99927.9971Elaine9.31759.32340.99630.99597.99907.9968House8.69838.73830.99600.99617.99927.9967Lena9.26469.25400.99590.99587.99917.9972Peppers8.90988.90970.99600.99617.99917.9969Average8.98889.00350.99610.99607.99917.9970


## 3.3. Comparison

Since most block-based VRAE schemes can completely recover the original image, in this section, we conduct embedding rate comparisons to demonstrate the advantages of our proposed scheme as compared to some state-of-the-art schemes. In each compared scheme, we simulate the optimal parameters to achieve the best embedding rate. For our proposed scheme, we adaptively choose the prediction direction for each image. We first compare the embedding rates among our scheme and eight related schemes [34–36, 39–43] for eight test images. In Table 6, the embedding rates of [34, 35] are relatively low, because the conventional reversible data hiding techniques of the spatial domain have been adopted. Schemes [36, 40–42] improve the embedding rate by vacating the spare room in each block’s bit plane. Scheme [39] adaptively compresses bit planes, so the embedding rate provided by this scheme is higher than the above bit plane schemes. Scheme [43] turns to compress the pixel differences; however, the spare room is not fully utilized. Since our scheme compresses the prediction errors and improves the prediction direction and block selection, it has the highest embedding rates for all eight images. Additionally, our proposed scheme has a noticeable improvement, that is, achieves 0.4994 bpp more than the second-highest ranked scheme [39]. Obviously, our scheme is superior to other state-of-the-art schemes, such that abundant additional secret data can be embedded into encrypted images.Table 6
Maximum embedding rate comparison in eight test images.
ImagesHuang et al. [34]Ge et al. [35]Qin et al. [40]Fu et al. [36]Wang et al. [41]Liu and Pun [42]Chen [43]Wang et al. [39]Proposed schemeAirplane0.14650.24230.77901.21221.15811.47531.68712.05202.5560Baboon0.02220.01320.22220.15700.22820.46460.31330.63221.0231Barbara0.06480.07820.38610.67710.62870.88160.86381.23491.6588Boat0.05570.06510.31490.65170.75261.11221.06861.41811.9056Elaine0.05380.06600.33210.58110.79041.05391.06761.32471.8793House0.14390.21430.82520.95150.82311.13271.32341.69732.2043Lena0.09480.13880.52311.02180.87491.35431.42201.74142.3516Peppers0.06190.08870.35610.87650.81761.23491.34361.62962.1469Average0.08050.11330.46730.76610.75921.08871.13611.46631.9657To further evaluate adaptability, we also compare the embedding rates on the BOSSBase dataset among our scheme and the six state-of-the-art schemes [36, 39–43] with higher embedding rates. As shown in Figure 9, the embedding rates in the first three schemes are relatively low. Only in our scheme and [39], embedding rates exceed 2 bpp, and our scheme has an improvement of 0.4929 bpp over [39]. Consequently, our proposed scheme is significantly superior to the state-of-the-art schemes and is applicable to a variety of images.Figure 9
Embedding rate comparison in BOSSBase.


## 4. Conclusions

The conventional block-based RDHEI schemes that vacate the room after image encrypting either perform suboptimally for small blocks or explore redundancy inefficiently. In this paper, to further improve the embedding rate, we use the block-based modulation technique to encrypt images. Then, an efficient predictor is proposed to generate a more centralized prediction error distribution. The Huffman coding technique is adopted to compress prediction errors in usable blocks so that the redundancy in each block can be adequately vacated. Experiment results demonstrate that the embedding rate has been significantly improved by 0.4929 bpp on average, in our proposed scheme, and is preferable compared to the state-of-the-art schemes. In the future, we will introduce some efficient deep-learning-based predictor and compression techniques to further improve the performance.



---

*Source: 9606116-2021-06-30.xml*