# Efficient Reversible Data Hiding Scheme for AMBTC-Compressed Images
## 3 Proposed Scheme
### Embedding Phase  
Assume that a \(P\times Q\) image \(I\) is encoded as an \(M\times N\) high mean table \(H\), an \(M\times N\) low mean table \(L\), and a \(P\times Q\) bitmap table \(B\), where \(M=P/4\) and \(N=Q/4\). After obtaining  
Figure 2: The current value \(H_{\text{cur}}\) and its four reference values. the three tables, the secret message \(S\) can be embedded by encoding the difference values of the two mean tables, \(H\) and \(L\), respectively. The final code stream \(CS\) generated by the proposed scheme will include four parts, which are guided information (\(IN\)), code stream \(CS_{H}\) of the high mean table \(H\), code stream \(CS_{L}\) of the low mean table \(L\), and code stream \(CS_{B}\) of the bit map table \(B\), as shown in Figure 3. As for guide information (\(IN\)), it indicates the basic data of the code stream, including the lengths of the secret message \(S\), codestream \(CS_{H}\), codestream \(CS_{L}\), size of cover image size, and value of \(m\). \(IN\) is used to tell the data receiver how they can determine the information of data during the extracting process. Figure 4 shows the flow chart of the proposed embedding phase. The detailed embedding algorithm is shown as follows. Step 1: Calculating difference value \(D\). Firstly, an inverse \"\(S\)\" scan path, shown in Figure 5, is used to scan the high mean table \(H\) and low mean table \(L\) into sequences of mean values \(SH\) (\(SH_{1}\), \(SH_{2}\),..., \(SH_{M\times N}\)) and \(SL\) (\(SL_{1}\), \(SL_{2}\),..., \(SL_{M\times N}\)), respectively. Then, calculate two different value sequences, \(DH\) and \(DL\), i.e., \(DH_{i+1}\) = \(SH_{i+1}\) - \(SH_{i}\) and \(DL_{i+1}\) = \(SL_{i+1}\) - \(SL_{i}\), where \(1\leq i\leq M\times N-1\). Figure 4: Flow chart of the proposed embedding phase. Figure 3: The structure of the code stream \(CS\). It is clear that the values of two difference sequences, \(DH\) and \(DL\), are in range \([-255,255]\). The embedding process of \(DH\) is similar to that of \(DL\). Therefore, to better explain, let \(D_{\rm i}\) be \(DH_{\rm i}\) (or \(DL_{\rm i}\)) and \(V_{\rm i}\) be the corresponding mean value of \(SH_{\rm i}\) (or \(SL_{\rm i}\)), respectively. Step 2: Encoding difference value \(D\). Due to the high correlation of adjacent values in the two mean tables, most of the difference values of \(D\) are ranged around 0. This property is used for embedding data. The value of \(D_{\rm i}\) will be encoded as follows. \[D_{i}^{\prime}=\left\{ \begin{array}{c}1||Sign||m\text{ {bits of }}/|D_{i}|\ ||b_{1}b_{2}b_{3}\text{ {if }}|D_{i}|<2^{m}\\ 0||(V_{i})_{2}\text{ {if }}|D_{i}|\geq 2^{m}\end{array} \right. \tag{4}\]  
where, for \(|D_{i}|<2^{m}\), the \(D_{i}\) is encoded by indicator \"1,\" followed by 1-bit of the sign of the value of \(D_{i}\), \(m\) bits of binary representation of the absolute value of \(D_{i}\), and concatenated by three secret bits \(b_{1}b_{2}b_{3}\). If \(D_{i}<0\), the sign of \(DH_{i}\) will be equal to 1; otherwise, the sign of \(DH_{i}\) will be equal to 0. Otherwise, if \(|D_{i}|\geq 2^{m}\), it is encoded by indicator \"0,\" and followed by eight bits of binary representation of the original mean value \(V_{\rm i}\). Then, the compression code of \(D_{i}\) is concatenated into the corresponding output code stream \(CS_{H}\) (or \(CS_{L}\)). Step 3: Code stream combination  
After all difference values of \(DH\) and \(DL\) are encoded completely, the final code stream \(CS\) is obtained by concatenating \(IN\), \(CS_{\rm H}\), \(CS_{\rm L}\), and the code stream \(CS_{\rm B}\) of the bitmap table. To clarify our embedding phase, Figure 6 shows an example of the embedding phase. Assume the AMBTC algorithm is performed, and a \(3\times 3\) high mean table is generated as shown in Figure 6a. Along the inverse \"S\" scan path, the difference values are calculated and shown in Figure 6b. Assume the secret message \(S\) is \"100011011011,\" and \(m=4\) is used. The first difference value \(D_{\rm i}\) of \(DH\) is equal to \"158,\" so \(|D_{\rm i}|=158\geq 2^{4}\).