# Reversible Data Hiding in Encryppted Images with Extended Parametric Binary Tree Labeling
## 1 Introduction  
Data hiding (DH) in plaintext images embeds secret information by a slight modification of pixel values that is imperceptible for human eyes [1]. To protect cover images, reversible data hiding (RDH) [2] is proposed, which can perfectly restore the cover image after the data are extracted. Nowadays, RDH is of enormous use in fields such as military communication and medical image management.  
There are several successful categories of RDH approaches. The first type is histogram shifting [3; 4; 5; 6], which first analyses the histogram of the image and then creates the available embedding bin by shifting bins on one side outward. The second is difference expansion [7; 8; 9], which doubles the difference between a pair of pixels to vacate embeddable state. The third is based on lossless compression [10; 11; 12], which vacates spare room for data embedding by compressing the cover image. The last is prediction error expansion [13; 14], which utilizes the spatial correlation between image pixel values to vacate available space. Some subsequent RDH methods improve or combine the above approaches to enlarge the data payload [15].  
[PERSON] [16] proposed the first work on reversible data hiding in encrypted images (RDHEI). Later on, improved versions were proposed by combining various image encryption techniques and data-hiding methods [17; 18; 19; 20]. In recent years, RDHEI schemes are commonly classified into two approaches, namely vacating room after encryption (VRAE) [21] and reserving room before encryption (RRBE) [22; 23; 24; 25]. In the frameworkof VRAE, RDH is performed directly on the encrypted image. The correlation between neighboring pixel values is disrupted by encryption, therefore, the redundant space is relatively less.  
RRBE leverages the correlation between neighboring pixel values to compress the cover image before image encryption and thus creates more spare room for data embedding. [PERSON] et al. [22] divided image pixels into two regions, A and B, according to a smoothness function. The least significant bits (LSBs) in region A were hidden into LSBs of region B and then the secret message was embedded into LSBs of region A. [PERSON] et al. [23] predicted the most significant bit (MSB) according to the correlation between a pixel and its neighbors, which improved the image quality and embedding capability. [PERSON] et al. [25] calculated the prediction error between adjacent pixels and made the use of the correlation between adjacent image pixels to further compress the code length.  
[PERSON] et al. [26] proposed a separable RDHEI, which allows independent execution of data extraction or image recovery. The cover image is first divided into blocks and a pixel in each block is assigned as the reference pixel. Values of the remaining pixels are predicted based on the reference pixels and classified into embeddable and non-embeddable groups. Through efficient labeling of embeddable pixels, spare room is vacated for data hiding. [PERSON] et al. [27] proposed an improved parametric binary tree labeling (IPBTL) RDHEI scheme. Instead of using sampling pixels as reference set, they defined the first row and the first column of the cover image as the reference set. Thus, the number of embeddable pixels can be greatly increased and the resulting data payload is expanded.  
The main features of the proposed EPBTL are as follows:  
1. Instead of directly recording the replaced pixel bits, we try to make the non-embeddable pixels self-recordable.
2. The reduction of auxiliary information significantly increases the total data payload.
3. Experimental results demonstrate that the proposed scheme outperforms state-of-the-art methods in embedding rate.  
The rest of this paper is organized as follows: Section 2 introduces the related work. Section 3 specifies the Proposed EPBTL scheme. Section 4 shows the experimental results. Section 5 concludes this paper and elaborates the future works.