# Reversible Data Hiding in Encrypted Image Based on Multi-MSB Embedding Strategy
## 2 Proposed Method
### Selection of Embeddable Pixels  
Suppose that the original image \(I\) is an 8-bit gray-scale image sized \(H\times W\). Then the value of each pixel \(I(i,j)\) belongs to [0,255] (\(1\leq i\leq H\), \(1\leq j\leq W\)). As shown in Figure 1(a), the content owner divides the original image into black, white, and grey parts. Then the black pixels are denoted as \(I_{B}\), the white pixels are denoted as \(I_{W}\), and the grey pixels at the edge are denoted as \(I_{ED}\). For each white pixel, there are some black pixels around it. According to the distribution of these black pixels, namely, the number and location of the surrounding black pixels, we divide these white pixels into three cases, I, II, and III, as shown in Figure 1(b). For case I, the white pixel has four diagonal black pixels surrounding it. For case II, two black pixels are located on the left and right of the white pixel, respectively. For case III, two black pixels are located on the upper and lower margins of the white pixel, respectively. Thus, the number of black pixels surrounding white pixels may be 2 or 4. Then, the local complexity of each white pixel \(I_{W}(i,j)\) is calculated by Equation (1). \[\Delta(i,j)=\sqrt{\frac{\sum_{k=1}^{u}\left(I_{B}^{k}(i,j)-I_{ave}(i,j) \right)^{2}}{u}},\ u=2\ \text{or}\ 4 \tag{1}\]  
where \(I_{B}^{k}(i,j)\) (\(k=1,\dots,u\)) are the black pixels which are surrounding with \(I_{W}(i,j)\), and \(I_{ave}(i,j)\) is the average value of these surrounding pixels. A large value of \(\Delta(i,j)\) indicates that the current white pixel \(I_{W}(i,j)\) is located in a relatively complex region. Thus, we define a threshold \(T\) that determines whether the current pixel is in a smooth region  
Figure 1: Tripartite relationship of the proposed method. Figure 2: (a) The original image is divided into three part: black pixels, white pixels, and grey pixels, (b) three types of white pixels. or in a complex region. If \(\Delta(i,j)\leq T\), then the current pixel \(I_{W}(i,j)\) is located in a smooth region, and we have \(I_{W}(i,j)\in I_{W}^{s}\); otherwise, \(I_{W}(i,j)\in I_{W}^{c}\), where \(I_{W}^{s}\) and \(I_{W}^{c}\) are two pixel sets which are located in a smooth region and complex region, respectively. In order to achieve accurate prediction for the current pixel, we only predict the pixels in \(I_{W}^{s}\). For the white pixels in three cases, I, II, and III, we use their corresponding nearest black pixels to predict them. Suppose that \(I_{W}^{s}(i,j)\) is the prediction value of \(I_{W}^{s}(i,j)\). According to different cases in Figure 2b, \(I_{W}^{s}(i,j)\) is predicted as  
\[I_{W}^{s}(i,j)= \begin{cases}\frac{I(i-1,j-1)+I(i-1,j+1)+I(i+1,j-1)+I(i+1,j+1)} {4}&(I)\\ \frac{I(i,j-1)+I(i,j+1)}{2}&(II)\\ \frac{I(i-1,j)+I(i+1,j)}{2}&(III)\end{cases}  \tag{2}\]  
According to prediction error between \(I_{W}^{s}(i,j)\) and \(I_{W}^{s}(i,j)\), the pixels in \(I_{W}^{s}\) are classified into two categories, and one of which is used to embed data. The criterion for pixel classification is  
\[\left|I_{W}^{s}(i,j)-I_{W}^{s}(i,j)\right|\leq 2^{m-1}-1 \tag{3}\]  
where \(m\)\(\in\) [3,4,5,6,7]. If the current white pixels satisfy Equation (3), it means that these pixels can be used for embedding data and denoted as \(I_{W}^{s}\). Otherwise, it means that these pixels cannot be used for embedding data and denoted as \(I_{W}^{s}\). Since secret data is embedded into the MSBs of the pixels to generate marked pixels in the proposed method, the MSBs of those pixels will be changed due to modification in the encoding phase. In order to guarantee reversibility, only the pixels which satisfy Equation (3) (i.e., \(I_{W}^{s}\)) can be used to embed data. The proof process is as follows. Note that the 1 th-\(m\)th LSBs of the marked pixels keep unchanged; these original bit planes can be restored after decryption operation. While the (\(m\)+1)th \(\sim\) 8 th MSBs of these pixels are changed after data embedding, we need to use the surrounding pixels to restore their original values in the decoding phase.