## 2 Proposed Method
### Content Owner's Work
#### 2.1.2 Vacating Room for Hiding Data  
Using the linear regression predictor \(\mathbf{LM}=\{w_{0},w_{1},w_{2},w_{3}\}\), which is trained from the original image, the predicted value \(p_{i,j}^{e}\) of the predictable pixel \(p_{i,j}\) is calculated by:  
\[p_{i,j}^{e}=\text{round}(w_{0}+w_{1}p_{i-1,j-1}+w_{2}p_{i-1,j}+w_{3}p_{i,j-1}) \,\text{ where }2\leq i\leq H,2\leq j\leq W. \tag{3}\]  
The prediction error \(e_{i,j}\) of \(p_{i,j}\) is calculated by:  
\[e_{i,j}=p_{i,j}-p_{i,j}^{e},\text{ where }2\leq i\leq H,2\leq j\leq W. \tag{4}\]  
For a standard 8-bit grayscale image, the range of \(e_{i,j}\) is \([-255,255]\). However, in most cases, \(p_{i,j}^{e}\) is close to \(p_{i,j}\), so the most prediction errors are concentrated in a small range around 0. Figure 4 shows the prediction error histograms of [PERSON] and Lena (Figure 5b,f in Section 4). As shown in the figure, the prediction errors are highly concentrated. Therefore, all of the prediction error information of the image has a lot of redundancy and can be compressed efficiently. For each predictable pixel \(p_{i,j}\), the original value can be calculated by the predicted value \(p_{i,j}^{e}\), and the prediction error \(e_{i,j}\). If all of the reference pixels maintain their original values, all of the predictable pixels can be recovered, row by row, using the predictor \(\mathbf{LM}\) and the prediction errors. Therefore, all of the predictable pixels in the original image can be replaced by the predictor \(\mathbf{LM}\) and the compressed prediction errors to vacate room for hiding data without losing any information. Figure 3: Reference pixels and predictable pixels. In the proposed method, the prediction errors are compressed by Huffman coding. Huffman coding is a variable length code scheme which construct the codewords with the shortest average code length according to the probability of the appearance of each character. The predictor \(\mathbf{LM}\) and the compressed prediction errors are stored in the MSBs of the predictable pixels, and the LSBs of the predictable pixels are used by the data hider for embedding secret data after the image has been encrypted. For an original image \(I\) sized \(H\times W\), the detail procedure of vacating room is as follows:  
Step 1: Calculate all the prediction errors \(e_{2,2},e_{2,3},\ldots,e_{H,W-1},e_{H,W}\) according to Equations (1) and (2) using the predictor \(\mathbf{LM}\). Step 2: According to the value distribution of the prediction errors, encode all of the prediction errors using Huffman coding. Connect all the encoded prediction errors row by row to form the bitstream \(\mathbf{BS}_{pe}=C(e_{2,2})C(e_{2,3})\ldots C(e_{H,W-1})C(e_{H,W})\), where \(C\big{(}e_{ij}\big{)}\) is the Huffman codeword of \(e_{ij}\). Figure 4: Prediction error histograms of Lena and Baboon. Figure 5: The eight test images. Step 3: Construct the Huffman codebook of the encoded prediction errors. The codebook \(\mathbf{CB}=\{N,(V_{1},L_{1},C_{1}),(V_{2},L_{2},C_{2}),\ldots,(V_{N},L_{N},C_{N})\}\), where \(N\) is the number of Huffman codewords, \(V_{i}\) is the value of the prediction error, \(L_{i}\) is the length of the codeword, and \(C_{i}\) is the codeword of \(V_{i}\). Step 4: From the most significant bit (MSB) plane to the lower bit plane, embed the length information L, the predictor \(\mathbf{LM}\), the Huffman codebook \(\mathbf{CB}\), and the encoded prediction error bitstream \(\mathbf{BS_{pe}}\) into the MSBs of all of the predictable pixels. The remnant bits of the predictable pixels are used as data hiding room at the data hider's side. Figure 6 shows an example of vacating room in a \(5\times 5\) image. To simplify the statement, we assumed that the trained linear regression-based predictor \(\mathbf{LM}=\{w_{0}=0,w_{1}=0,\)\(w_{2}=1,w_{3}=0\}\) and that its binary representation is \((0010)_{2}\). Using the predictor \(\mathbf{LM}\), the prediction errors of the predictable pixels were calculated and compressed by Huffman coding.