## 2 Proposed Scheme
### Secret Embedding and Encryption Stage  
For clarity, the stage is divided into four steps, namely prediction, difference calculation, Hamming coding calculation and shuffling, and secret embedding and encryption. The details of each step are described as follows. In the prediction step, since pixels are similar to their neighboring pixels, the pixels located in the first row and first column are regarded as unchanged seed pixels, named reference pixels, which are used to predict the neighboring pixels. Aside from the reference pixels, the predicted pixels represented by \(\hat{p}(i,j)\) are calculated via Equation (1) based on the neighboring pixels of the pixel \(p(i,j)\), where \((i,j)\) is the location of the pixel in the given image \(O\), \(t_{1}\) and \(t_{2}\) are thresholds that control the predicted value close to \(p(i,j)\). For example, as shown in Figure 1, the neighboring pixels of \(p(2,2)\) are \(p(1,1)\), \(p(1,2)\) and \(p(2,1)\) and the corresponding pixel values are 100, 102 and 105, respectively. Because \(p(1,1)\) is less than \(p(1,2)\) and \(p(2,1)\), \(\hat{p}(2,2)\) will be 106 when \(t_{1}\) is 1. Next, in the difference calculation step, we use Equation (2) to convert \(p(i,j)\) and \(\hat{p}(i,j)\) into two bitstreams. The \(k\)-th bits corresponding to \(p(i,j)\) and \(\hat{p}(i,j)\) are respectively expressed as \(p^{k}(i,j)\) and \(\hat{p}^{k}(i,j)\), where \"mod\" is a modular operation. For example, if \(p(2,2)\) is equal to 108, then \(p^{8}(2,2)\) is 0. Then, Equation (3) is used to calculate the difference between the two numbers \(p(i,j)\) and \(\hat{p}(i,j)\), where \(\oplus\) is the exclusive OR operation. As for the example shown in Figure 1, if \(p(2,2)\) and \(\hat{p}(2,2)\) are 108 and 106, the result of Equation (3) is 00000110, denoted by \(x(2,2)\). With Equation (4), the \(k\)th most significant bit of \(x(i,j)\) equal to 1 is denoted by \(c^{d}(i,j)\). In the same example, if \(x(2,2)\) is equal to 00000110, the value \(c^{d}(2,2)\) will be 3. Next, \(c^{*}(i,j)\) is calculated with Equation (5) to represent the number of consecutive MSBs of the original pixel equal to that of its predicted pixel. For example, the value of \(c^{*}(2,2)\) is 5. In other words, in the example, five MSBs of the pixel \(p(2,2)\) can be predicted by \(\hat{p}(2,2)\). The value of the 6 th MSB of \(p(i,j)\) can be recovered as the flipped value of \(\hat{p}(2,2)\). Thus, the \(c^{*}(i,j)+1\) MSB of the pixel \(p(i,j)\) can be used to hide the secret. \[\hat{p}(i,j)=\left\{ \begin{array}{ll}p(i-1,j-1)&\text{if }p(i-1,j-1)=p(i-1,j)=p(i,j-1)\\ max(p(i-1,j),p(i,j-1))+t_{1}&\text{if }p(i-1,j-1)<min(p(i-1,j),p(i,j-1))\\ min(p(i-1,j),p(i,j-1))+t_{2}&\text{if }p(i-1,j-1)>max(p(i-1,j),p(i,j-1))\\ p(i,j-1)+p(i-1,j)-p(i-1,j-1)&\text{otherwise.}\end{array} \right. \tag{1}\]  
\[p^{k}(i,j)=\frac{p(i,j)\text{ mod }2^{k}}{2^{k-1}},k\text{ for }8\text{ to }1 \tag{2}\]  
\[x^{k}(i,j)=p^{k}(i,j)\oplus\hat{p}^{k}(i,j),\,k=1,2,\,...,\,8 \tag{3}\]  
\[c^{d}(i,j)=\operatorname*{arg\,max}_{k}x^{k}(i,j)=1,\,k=1,2,\,...,\,8 \tag{4}\]  
\[c^{*}(i,j)=8-c^{d}(i,j) \tag{5}\]  
In the Hamming coding calculation and shuffling step, when applying Hamming coding matrix [36], we convert the \(c^{*}(i,j)\) into a bit stream as an indicator, depicted by (\(w_{1}w_{2}w_{3}\)). Noted that since (\(w_{1}w_{2}w_{3}\)) can only appear in eight cases, but there are actually nine cases in the difference calculation, the cases are defined according to smooth and complex images. The image judges the type of image based on the higher capacity in the smooth type encoding or complex one. The image type (smooth and complex are marked as \"s\" and \"c\", respectively) is treated as a parameter saved in the database. If it is a smooth image, values of \(c^{*}(i,j)\) equal to 0 and 1 fall into the same case. Therefore, with regard to  
Figure 1: A sample prediction for a complex image.