# A Reversible Data-Hiding Method with Prediction-Error Expansion in Compressible Encrypted Images
## 3 Proposed Method
### Procedure of Encryption and Data hiding
#### 3.2.2 Data Hiding  
The data-hiding process is divided into three parts: histogram modification, PEE-HS, and block integration. We describe each part below. * Histogram modification: Since PEE-HS is used for data hiding, overflow (OF) or underflow (UF) may be caused in the value of each pixel. With the following steps, our method preliminarily modifies an image histogram in order to prevent OFs and UFs in pixel values. \\ Step2-1: & Explore a zero point (\(ZP\)) that is a bin with no pixels in an encrypted image histogram. \\ Step2-2: & To prevent UFs, add 1 to pixels with a value lower than \(ZP\). \\ \end{tabular}  
Figure 4: Outline of proposed method. Figure 5: Encryption and data-hiding procedure of proposed method. Step2-3: Repeat Steps 2-1 and 2-2 \(L+1\) times. Here, \(L\) is a threshold used in data hiding. Step2-4: Explore a \(ZP\) in the image histogram. Step2-5: To prevent OFs, subtract 1 from pixels with a value higher than \(ZP\). Step2-6: Repeat Steps 2-4 and 2-5 \(L+1\) times. We needed to exclude eight pixels from the top-left corner of encrypted images from the above steps and the following data-hiding process. An 8-bit value of threshold \(L\) was embedded into these pixels. Additionally, if there was no \(ZP\) in the histogram, we focused on two neighboring bins with the lowest sum of frequencies. These bins were integrated into a single bin, and another bin was emptied (\(LP\)). We built a location map where the original pixel values with the two neighboring bins were recorded in order to identify their original pixel values in the restoration process. It is necessary to embed the value of \(ZP\) or \(LP\) with an arbitrary payload to perfectly retrieve the original image. In the case of \(LP\), the location map should be stored along with \(LP\). * Prediction-error expansion and histogram shifting: We extended an RDH method on the basis of PEE-HS for stereoimages [16] and incorporated it into the proposed method. Our method embeds payload bits into each block, which is the same block as that in the encryption process. We describe the data-hiding procedure as follows. Step3-1: For pixels \(p_{i,j}\) in each block, where \(0\leq i<B_{x}\) and \(0\leq j<B_{y}\), predicted values \(\hat{p}_{i,j}\) are derived from \[\hat{p}_{i,j}= \begin{cases}\min(p_{i-1,j},\ p_{i,j-1}),\\ \quad\text{if }p_{i-1,j-1}\geq\max(p_{i-1,j},\ p_{i,j-1})\\ \max(p_{i-1,j},\ p_{i,j-1}),\\ \quad\text{if }p_{i-1,j-1}\leq\min(p_{i-1,j},\ p_{i,j-1})\\ p_{i-1,j}+p_{i,j-1}-p_{i-1,j-1},\ \text{otherwise}.\end{cases} \] (1) Here, prediction values \(\hat{p}_{0,j}\) and \(\hat{p}_{i,0}\) cannot be obtained with (1). Thus, we define \[\hat{p}_{0,j}=p_{0,j-1},1\leq j\leq B_{y},\] (2) \[\hat{p}_{i,0}=p_{i-1,0},1\leq i\leq B_{x}.\] (3) The top-left pixel \(p_{0,0}\) in each block was excluded from data hiding for reversibility. Step3-2: Derive prediction errors \(e_{i,j}\): \[e_{i,j}=\hat{p}_{i,j}-p_{i,j}.\] (4) Step3-3: in the prediction-error histogram, empty bins are derived in the range of \([-2L-1,-L-1]\) and \([L+1,2L+1]\) in accordance with the following equation. \[e^{\prime}_{i,j}= \begin{cases}e_{i,j}+(L+1),&\text{if }\ e_{i,j}\geq L+1\\ e_{i,j}-(L+1),&\text{if }\ e_{i,j}\leq-(L+1)\\ e_{i,j},&\text{otherwise},\end{cases} \] (5) where \(e^{\prime}_{i,j}\) denotes the prediction error after shifting. Figure 6a shows an example of a histogram shift in the case of \(L=2\). Figure 6: Procedure of data hiding (\(L=2\)). (**a**) Derivation of empty bins, (**b**) data hiding for pixels with \(|e^{\prime}_{i,j}|=2\), (**c**) data hiding for pixels with \(|e^{\prime}_{i,j}|=1\), (**d**) data hiding for pixels with \(e^{\prime}_{i,j}=0\), (**e**) data hiding for pixels with \(e^{\prime}_{i,j}=0\). (6)  
(7)  
In this case, \(\tilde{e}^{\prime}_{i,j}\) is updated by (8). (8)  
* Block integration: lastly, we integrate all the blocks into a marked encrypted image \(\tilde{I}_{\text{Genc}}\). The LSBs of eight pixels from the top-left pixels in marked encrypted images are replaced with the value of \(L\).