## 2 The Proposed RDHEI Method
### Room Reservation and Image Encryption
#### 2.1.1 Pixel Prediction
Figure 4 shows the original Lena image, its histogram, the prediction error Lena image, obtained by using the GAP predictor, and its histogram. Throughout this paper, in all histogram figures, the horizontal axis is dedicated to representing pixel intensities, while the vertical axis is employed to illustrate the frequency associated with each intensity level. From Figure 4d, it can be clearly seen that most of the prediction errors are very close to 0. Moreover, Figure 5 shows the original Jetplane image, its histogram, the prediction error Jetplane image, and its histogram. Furthermore, Figure 6 illustrates two bit-plane decomposition schemes that have been applied to the Lena image. The columns represent the bit planes, starting from the sign bit and progressing from the least significant bit to the most significant bit. The rows show the bit-plane decompositions of the original image and the prediction error image achieved through the utilization of the GAP predictor. Figure 4: (**a**) The Lena image and (**b**) its histogram. (**c**) The prediction error Lena image and (**d**) its histogram obtained by using the GAP predictor. Figure 5: (**a**) The Jetplane image and (**b**) its histogram. (**c**) The prediction error Jetplane image and (**d**) its histogram obtained by using the GAP predictor. Figure 6: The Lena image undergoes two bit-plane decomposition schemes. The columns represent the bit planes, starting from the sign bit and progressing from the least significant bit to the most significant bit. The rows display the bit-plane decompositions of the original image and the prediction error image achieved through the GAP predictor. In our method, we propose to map the prediction errors to non-negative values in order to reduce the error range from \([-255,255]\) to \([0,255]\) by applying Equation (1). \[e(u,v)=\left\{ \begin{array}{ll}x(u,v)&if|e(u,v)|>127\\ (|e(u,v)|<<1)|SIGN&otherwise\end{array} \right., \tag{1}\]  
where \(|.|\) denotes the absolute value function, \(<<\) is the bitwise left shift operator, and \(|\) is the bitwise OR operator. \(SIGN\) is a binary variable that contains 1 if the predicted error \(e(u,v)\) is negative and 0 otherwise. It should be noted that, if the absolute value of the error is less than or equal to 127, \(|e(u,v)|\leq 127\), only 7 bits are required to encode it, and additionally one more bit representing the sign is concatenated to its binary representation for ensuring that the process is fully reversible. Finally, when the error is greater than 127 or less than \(-127\), it is considered an overflow pixel and modified by \(e(u,v)=x(u,v)\). Figure 7a,c show the bit-planes of the mapped prediction error images for Lena and Jetplane images, respectively. Algorithm 1 details the process for the prediction error mapping. The outputs of this algorithm are the mapped prediction error image as well as the binary label map. This label map is used to distinguish between the different formulas used in identifying each prediction error. It is a binary map with the same size of the original image, which is filled as follows: \(label\,Map(u,v)\) is set to 1 for the overflow pixels and 0 otherwise. It is also compressed by using arithmetic coding [24; 29; 30; 31] and then inserted into the mapped prediction error image as an auxiliary information. It is worth mentioning that for most of the tested images, this label map contains zeros only, and consequently, only one bit is required to represent it. For a few images, even if the label map contains non-zero values, a large number of 0 and a fairly small number of 1 are found, which leads to an effective compression by arithmetic coding and therefore a very small number of bits is required for its representation. Using this label map with the mapped prediction errors instead of representing the prediction error image with 9 bit planes, including the sign bit plane and bit planes from the LSB to the MSB, offers a significant advantage in terms of efficiency.