## 3 Histogram-Based Reversible Data Hiding with Quadtree Decomposition
### The Three-Round Embedding Process  
In conjunction with the conventional histogram-based reversible data hiding described in Section 2, we propose the three-round embedding process in Figure 4 with the characteristics of original image by using quadtree decomposition. The proposed scheme can be briefly outlined as follows. Figure 3: **(a)** The Lena test image. **(b)** After quadtree decomposition of Lena. **Round 1. **: Perform the quadtree decomposition to the original image, **X**, and obtain different block sizes for the composition of original image. Find the luminance value of the zero point of the whole image. Save each block size and the luminance value of max point at the corresponding position as the block map (BM), **B**, depicted in Figure 4(a). **Round 2. **: Apply the histogram-based reversible data hiding for embedding information, \(S\), to each block in the original image **X**. Output the image containing \(S\), and call it **X'**. We can directly employ Figure 1(a) in this Round, and represented by Figure 4(b). **Round 3. **: After completing data embedding in Round 2, we apply the histogram-based reversible data embedding again, and embed the block map **B** into **X'**. Call the output image of this round as **X\"**. Transmit the side information \(K\) to the decoder, shown in Figure 4(c). Here we go into more details in each of the three rounds. At Round 1, we demonstrate the procedure in Figure 4, with the original \"Lena\" image in Figure 3(a). We can easily find that after quadtree decomposition, based on the characteristics of original image, it can be decomposed into square blocks with sizes among 16 \(\times\) 16, 32 \(\times\) 32, and 64 \(\times\) 64, in Figure 3(b). Homogeneity of each block of original image can be determined by a threshold \(T\), which may be calculated by:  
\[ \begin{cases}\big{(}\text{max}\big{(}\text{block value}\big{)}-\text{min} \big{(}\text{block value}\big{)}\big{)}\geq T&\Rightarrow\ \ \text{Keep decomposition};\\ \big{(}\text{max}\big{(}\text{block value}\big{)}-\text{min}\big{(}\text{ block value}\big{)}\big{)}<T&\Rightarrow\ \ \text{Stop}.\end{cases}  \tag{1}\]  
We set \(T=\alpha\cdot 255\), \(\alpha\in\big{[}0,1\big{]}\). The value of \(\alpha\) can be adjusted by the users. Thus, for smaller threshold values, more blocks will be produced, and the size of the block map **B** will grow accordingly. Next, at Round 2 of Figure 4(b), each square block in Figure 3(b) can be regarded as a small image. From the descriptions in Section 2, after the embedding with histogram-based reversible data hiding, the two luminance values for max and zero points, namely, \(a_{i}\) for the max point and \(b_{i}\) for the zero point for the \(i\) -th block, respectively, and each can be represented by 8 bits, are served as the side information. Without loss of generality, we assume that \(a_{i}<b_{i}\), \(\forall i\). Under the extreme case when the original image is highly active, which implies more blocks, 16 \(\times\) 16 each, would be necessary for decomposing the original image. Then, it would lead to \(\frac{512}{16}\times\frac{512}{16}=\)1024 blocks in total, and 1,024 \(\times\) (8 + 8) = 16,348 bits of side information are produced. Because only the value \(a_{i}\) in Figure 3(b) is required for data extraction in each block, we set all the values of \(b_{i}\) to be the luminance value at zero point of the whole image, \(b\), to reduce the overhead. By doing so, at most 1,024 \(\times\) 8 + 8 = 8,200 bits of side information of the block map **B** is produced. For the better representation the quadtree decomposition, approaches are the same in the method in [12,13] (called the quadtree partition, QP) as that in our methods (_i.e._, the block map **B**). Both employ the pyramidal hierarchy for data transmission. We can perform a brief depiction with the help of Figure 5.  
Figure 4: **(a)** Diagram for Round 1. **(b)** Diagram for Round 2. **(c)** Diagram for Round 3.