## 2 Adjacent Pixel Difference (APD)  
The histogram of Lena, a 512 x 512 gray scale image, is shown in Figure 1a. The pixel values with the highest and second-highest frequencies were PP\({}_{1}\) (peak point 1) and PP\({}_{2}\) (peak point 2), respectively. The pixel values with zero frequencies located closest to the left and right of PP\({}_{1}\) and PP\({}_{2}\) are CZP\({}_{1}\) (closest zero point 1) and CZP\({}_{2}\) (closest zero point 2), respectively. Figure 1a shows that CZP\({}_{1}\) = 33, PP\({}_{1}\) = 153, PP\({}_{2}\) = 154, and CZP\({}_{2}\) = 235. [PERSON], [PERSON], [PERSON], and [PERSON] proposed the NSAS technique, a reversible data hiding algorithm using a histogram shift [1]. As mentioned previously, the NSAS technique has a weakness; the number of confidential data bits that can be embedded is limited to 5701 bits, which is the sum of h(PP\({}_{1}\)) and h(PP\({}_{2}\)). The variable h(PP\({}_{1}\)) represents the frequency of the pixel value PP\({}_{1}\). [PERSON] et al. proposed the adjacent pixel difference (APD) technique [2] that improved the NSAS technique. The APD technique greatly increases the number of confidential data bits that can be embedded in the cover image by effectively using the property that adjacent pixels have similar values. In the APD technique, the cover image is scanned from left to right and top to bottom in inverse s-order to generate the cover image sequence (C), a sequence of pixel values. Equation (1) is applied to C to generate an adjacent pixel difference sequence (D) consisting of pixel value differences between adjacent pixels. As adjacent pixels are generally similar to each other, many elements of D have values close to zero. Therefore, in the histogram of D, the frequency at zero and values close to zero increases significantly. This is due to the existence of local similarity in images. \[\mathrm{D_{i}}=\left\{ \begin{array}{ll}\mathrm{C_{i}}&\mathrm{if\ i=0}\\ \mathrm{C_{i-1}-C_{i}}&\mathrm{if\ 1\leq i\leq n-1}\end{array} \right.\mathrm{ where\ n=(image\ height)\cdot(image\ width)} \tag{1}\]  
The histogram of D generated by applying Equation (1) to the cover image sequence of Lena is shown in Figure 1b where h(PP\({}_{1}\)) is 25,010 bits, and h(PP\({}_{2}\)) is 23,414 bits. These values were much larger than those in Figure 1a. In the APD technique, as the histogram of D was shifted to embed confidential data, the maximum number of data bits that could be embedded was h(PP\({}_{1}\)) + h(PP\({}_{2}\)) = 48,424 bits, which was the sum of the frequencies at peak points PP\({}_{1}\) and PP\({}_{2}\). Therefore, the APD technique could embed 42,723 more bits than the NSAS technique, and the number of confidential data bits that could be embedded was 8.5 times more than the ones embedded in NSAS. The data embedding procedure of the APD technique is shown in Figure 2. The maximum number of data bits that can be embedded in the cover image is h(PP\({}_{1}\)) + h(PP\({}_{2}\)), as shown in Step 5 of Figure 2. The symbol (PP\({}_{j}\), CZP\({}_{j}\)) used in Equation (2) of Figure 2 represents a set of integers greater than PP\({}_{j}\) and less than CZP\({}_{j}\). If PP\({}_{j}\) is 1 and CZP\({}_{j}\) is 5, then (1, 5) is {2, 3, 4}. The symbol [PP\({}_{j}\) +sd\({}_{j}\), CZP\({}_{j}\)] used in  
Figure 1: The histogram of Lena and adjacent pixel difference sequence (D). (**a**) The histogram of Lena and (**b**) the histogram of the adjacent pixel difference sequence (D)Equation (7) of Figure 3 represents a set of integers greater than or equal to \(\text{PP}_{\text{j}}\) +sd\({}_{\text{j}}\) and less than or equal to \(\text{CZP}_{\text{j}}\). If \(\text{PP}_{\text{j}}\) +sd\({}_{\text{j}}\) is 1 and \(\text{CZP}_{\text{j}}\) is 5, then [1,5] is [1, 2, 3, 4, 5].