# Reversible Data Hiding in Encrypted Images Based on the Mixed Multi-Bit Layer Embedding Strategy
## 3 Proposed Scheme
### Pre-Processing  
In the proposed scheme, pre-processing refers to the stage before image encryption. The main function is to reserve room. This section carefully illustrates the steps. It contains two-round segmentation, parameters design, auxiliary data generation, and other steps. * First-round segmentation. Input the cover image with the size of \(M\times N\) and decompose it into non-overlapping blocks with the size of \(m\times n\) in the main order of rows. The number of pixels in a block is \(l_{1}=m\times n\). The block is represented as the column vector \(X=\{x_{1},x_{2},\dots\ x_{l_{1}}\}\). Next, set threshold parameter \(T\) and calculate differences. \(T\) takes the exponent of 2, as the condition of whether the block can be hidden. Then taking the first pixel \(x_{1}\) of each block as a reference, calculate the difference between \(X\) and \(x_{1}\), and record it as:  
\[D=\big{\{}d_{1},d_{2},\dots d_{l_{1}}\big{\}}. \tag{1}\]  
Let the maximum value of \(D\) be \(\max(D)\). If \(\max(D)<T\), it means that it is a smooth block. Then mark the block as an AHB by setting LSB of \(x_{1}\) to 1, and type \(BT_{1}\). Otherwise, mark the block as an UHB by setting LSB to 0. Since the hidden room needs to be reserved in the AHBs, the auxiliary data generated by them is recorded. The auxiliary data for each AHB are as follows. The binary representation of (1) is:  
\[D_{01}=\big{\{}(d_{1})_{01},(d_{2})_{01},\dots(d_{l_{1}})_{01}\big{\}}. \tag{2}\]  
Figure 1: The proposed scheme based on the mixed multi-bit layer embedding strategy. The positive and negative of \(D\) are recorded by parameter \(w\) with 1 bit. The length of \(D_{01}\) is related to \(T\), usually \(\log_{2}\left(T\right)\) bit. To reach pixels recovery without loss at the receiver, \(w\) and the \(D_{01}\) are combined to generate the auxiliary data \(E_{1}\), which is represented as follows:  
\[E_{1}=\Big{\{}w_{1},\left(d_{1}\right)_{01},w_{2},\left(d_{2}\right)_{01}, \ldots w_{l_{1}},\left(d_{l_{1}}\right)_{01}\Big{\}}. \tag{3}\]  
* Second-round segmentation. After first-round segmentation, the image blocks are divided into AHBs and UHBs. Then, the UHBs are used for second-round segmentation. First, the UHB is divided into two sub-blocks, \(P\) and \(Q\), to expand the embedded space. They are generated by the segmentation of the column vector \(X\) and represented as follows:  
\[P=\big{\{}x_{1},x_{2},\ldots x_{l_{2}}\big{\}},Q=\big{\{}x_{l_{2}+1},x_{l_{2}+2 },\ldots x_{l_{1}}\big{\}}. \tag{4}\]  
Second, the sub-blocks are classified in the same way as the first round, and then the smooth blocks are marked as AHBs, type \(BT_{2}\), and the other blocks are complex, marked as UHBs, type \(BT_{3}\). Unlike the first round, the marker bit for \(P\) is in the penultimate position of \(x_{l_{1}}\) and the marker bit for \(Q\) is still in the LSB. After the above processing, the whole image is marked into three categories. The description of the blocks is shown in 0. Table 1 describes the characteristics of the three types of blocks. Column 2 shows the block type. Column 3 shows the length, \(l_{1}\), \(l_{2}\), or \(l_{1}\),\(l_{2}\). Column 4 shows the number of each type. The last column shows the reference pixels in different types of blocks, which may be \(x_{1}\) or \(x_{l2+1}\). The above process of classification and position marking is shown in Figure 2. \begin{table}
\begin{tabular}{c c c c c} \hline
**Block Type** & **Classification** & **Length** & **Number** & **Reference Pixel** \\ \hline \(BT_{1}\) & AHB & \(l_{1}\) & \(N_{1}\) & \(x_{1}\) \\ \(BT_{2}\) & AHB & \(l_{2}(P)\) or \(l_{1}\),\(l_{2}(Q)\) & \(N_{2}\) & \(x_{1}\) or \(x_{l2+1}\) \\ \(BT_{3}\) & UHB & \(l_{1}\)-\(l_{2}(Q)\) or \(l_{2}(P)\) & \(N_{3}\) & \(x_{l2+1}\) or \(x_{1}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Description of different types of blocks. Figure 2: _Cont._  
Figure 2 gives the results of block processing after the steps above. The sub-figures contain schematic diagrams of two-round block segmentation, classification, and position marking.