# Reversible Data Hiding in Encrypted Color Halftone Images with High Capacity
## 3 Proposed Scheme
### Extraction and Recovery
#### 3.3.1 Watermark Extraction  
When the receiver has only the data-hiding key \(K_{d}\), he can extract the watermark from stego image \(\mathbf{C}\). The receiver first divides the image into channel images \(\mathbf{C}_{R}\), \(\mathbf{C}_{G}\), and \(\mathbf{C}_{B}\). For stego image \(\mathbf{C}_{R}\), he separates it into four images \(\mathbf{T}_{R^{\prime}}\), \(\mathbf{F}_{R^{\prime\prime}}\), \(\mathbf{S}_{R^{\prime\prime}}\), and \(\mathbf{T}_{R^{\prime\prime}}\). Stego images \(\mathbf{T}_{R^{\prime}}\) and \(\mathbf{T}_{R^{\prime\prime}}\) are divided into \(\alpha\times\beta\) non-overlapping blocks, each of which is denoted as \(\mathbf{W}_{fi}\), \(j=1,\cdots,w\) and \(\ell=1,2\). Converteach of \(\mathbf{W}_{1j}\) to a column vector \(\mathbf{y}^{\prime}_{3j}\), and, the following equation is calculated to obtain the encrypted watermark blocks \(\mathbf{\theta}_{3j}\) according to Equation (8)  
\[\mathbf{\theta}_{3j}=\mathbf{D}_{3j}\times\mathbf{y}^{\prime}_{3j} \tag{11}\]  
where \(\mathbf{D}_{3j}\) is pseudo-random binary matrix generated by \(K_{d}\). Then, read the first four bits of \(\mathbf{W}_{2j}\) and convert them to a column vector \(\bar{\mathbf{z}}_{3j}\). Next, replace the first four bits of every block by  
\[\mathbf{z}^{\prime}_{3j} =\mathbf{z}_{3j}\oplus\mathbf{\theta}_{3j} \tag{12}\] \[=\mathbf{z}_{3j}\oplus\mathbf{\theta}_{3j}\oplus\mathbf{\theta}_{3j}\] \[=\mathbf{z}_{3j}\]  
After that, stego image \(\mathbf{S}_{R^{\prime}}\) is acquired. We divide \(\mathbf{S}_{R^{\prime}}\) and \(\mathbf{S}_{R^{\prime\prime}}\) into \(1\times 8\) non-overlapping blocks, each of which is denoted as \(\mathbf{E}_{\ell j},\ j=1,\cdots,w\) and \(\ell=1,2\). Convert each of \(\mathbf{E}_{1j}\) into vectors \(\mathbf{y}^{\prime}_{2j}\), and then into the encrypted watermark blocks \(\mathbf{\theta}_{2j}\) by calculating  
\[\mathbf{\theta}_{2j}=\mathbf{D}_{2j}\times\mathbf{y}^{\prime}_{2j} \tag{13}\]  
Next, the first four bits of each block of \(\mathbf{E}_{1j}\) are converted to column vectors \(\bar{\mathbf{z}}_{2j}\). Then, replace them by  
\[\mathbf{z}^{\prime}_{2j}=\bar{\mathbf{z}}_{2j}\oplus\mathbf{\theta}_{2j} \tag{14}\]  
Thus, stego image \(\mathbf{F}_{R^{\prime}}\) is achieved, and we also get cover image \(\mathbf{R}\) and encrypted watermark blocks \(\mathbf{\theta}_{1j}\) by performing the same process using \(\mathbf{F}_{R^{\prime}}\) and \(\mathbf{F}_{R^{\prime\prime}}\). In addition, cover images \(\mathbf{G}\) and \(\mathbf{B}\) as well as watermark blocks \(\mathbf{\theta}_{\gamma^{\prime}j}\) (\(\gamma^{\prime}\)\(=4,\cdots,9\)) are also generated from stego images \(\mathbf{C}_{G}\) and \(\mathbf{C}_{B}\). We concatenate \(\mathbf{\theta}_{\gamma j}\) to column vectors \(\mathbf{\theta}_{\gamma i}\) and get watermark \(b_{\gamma i}\) by calculating  
\[b_{\gamma i}=\theta_{\gamma i}\oplus p^{\prime}_{\gamma i} \tag{15}\]  
where \(\gamma\)\(=1,\cdots,9\), \(p^{\prime}_{\gamma i}\) is determined via standard stream cipher using data-hiding key \(K_{d}\). Finally, images \(\mathbf{R}\), \(\mathbf{G}\) and \(\mathbf{B}\) are merged to compose cover image \(\mathbf{I}\).