## 4 Simulation Results  
We perform the following simulations for the evaluation of our algorithm. Requirements are evaluated below in comparison with conventional algorithm, including:  
* the output image quality, represented by PSNR, after hiding the user-defined data;
* the capacity, represented by bits, of the user-defined binary random data;
* the size of the overhead. The first two requirements are easy for making comparisons. For the third one, we find that in Figure 3(b), the block sizes after performing quadtree decomposition are different. Therefore, the different block sizes compose of the block map **B** for making data embedding and extraction possible. In order to make fair comparisons, we divide the original image into blocks with the same sizes of \(512\times 512\), \(256\times 256\), \(128\times 128\), \(64\times 64\), \(32\times 32\), and \(16\times 16\), respectively. In contrast with quadtree decomposition, these configurations have regular patterns, and only one block size needs to be included into the block map. Hence, except for the block size, only luminance of the max point in each block should be included in the block maps. On the contrary, with quadtree decomposition, we may expect the more overhead in the block map **B** because the side information of each block is composed of the block size and the luminance of max point. To make fair comparisons, even though the block map with quadtree decomposition is larger than the other cases, Round 3 of the  
Figure 6: **(a)** The output image **X”** in Figure 3(c), with \(\text{PSNR}=51.13\) dB. **(b)** Corresponding histogram with **X”**. Correlation coefficient = 0.9808.  
embedding process comprises the block map even though some degradation in output image quality can be expected. To embed block map **B** in Section 3.1, in the Lena image in Figure 6, we choose \(a^{\prime}\) = 159 and \(c^{\prime}\) = 237 to serve as the side information, and the block map **B** can be embedded. Table 1 depicts the comparisons between the image quality and embedding capacity under a variety of block sizes. For the block size of \(512\times 512\), we find that the capacity is 0.0113 bit/pixel (bpp), or 2,958 bits in the 512 \(\times\) 512 image, with the PSNR of 53.54 dB. These serve as a reference corresponding to existing scheme in [8]. When the block size gets smaller, more capacity can be embedded at the expense of somewhat degraded quality. Because the image qualities under all the block sizes are larger than 48.13 dB, we can claim that these qualities are acceptable. With quadtree decomposition, the performances accessed by quality and capacity lie between the block sizes of \(32\times 32\) and \(256\times 256\). If we set the PSNR the same, we can see that with quadtree decomposition, our algorithm can hide more capacity than the 64 \(\times\) 64 case. In Figure 6, we present the output after reversible data hiding and corresponding histogram for subjective evaluation. Figure 6(a) denotes the output **X\"** of Figure 3(c), with the PSNR of 51.13 dB. Figure 6(b) depicts the output histogram, and it is also highly correlated with Figure 2(a), with the correlation coefficient of 0.9808. After embedding 14,303 random bits with our scheme or the capacity of 0.0546 bpp, the quality is still guaranteed. Table 2 represents the simulation results with different test images. The image sizes are all \(512\times 512\) for making fair comparisons. Regarding to the image qualities, they are all more than 48.13 dB. Corresponding capacities are also provided, and we observe that capacities are highly correlated to the characteristics of original images, ranging from 0.0493 to 0.3651 bpp. Next, the increases for the quadtree decomposition over existing method are provided. For instance, for the Lena image, the capacities for the quadtree and the conventional methods [8] are 0.0546 and 0.0113 bpp, respectively. Therefore, we can easily calculate the increase in percentage by \(\left(\frac{0.0546}{0.0113}-1\right)\times\)100%\(=284\%\).