## 1 Introduction  
Data hiding is an important technique for embedding confidential data in cover media such as digital images. A stego-image is generated by hiding confidential data in a cover image, and the confidential data are extracted from the stego-image. Imperceptibility is vital in data hiding, to make it impossible for humans to know whether confidential data is hidden in stego-images [1]. To meet this requirement, the quality of the stego-image must be excellent. Most data hiding techniques that aim to improve the stego-image's image quality cause distortion in the recovered cover image after extracting the confidential data from the stego-image. Thus, the recovered cover image and the original cover image are inconsistent [2]. The reversible data hiding technique, in which the recovered cover image matches the original cover image, is important in digital image watermarking, military, medical, and digital library [3] applications. Various reversible data hiding techniques have been recently proposed [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38]. Various techniques have been proposed to hide data using the least significant bit (LSB) of image pixels [4; 5; 6; 7; 8; 9]. The data hiding techniques using the LSB of a pixel has a disadvantage in that the restored cover image does not match the original cover image because the LSBs are changed. Data hiding based on wavelet analysis, especially multi-resolution analysis (MRA), has been widely used, and one of the problems with data hiding methods is the visibility of the information contained in the available distributed images [10; 11; 12; 13; 14; 15]. Data hiding techniques using an additional reference matrix are proposed to increase embedding efficiency [16; 17; 18; 19], and those using pixel value ordering (PVO) are also used [20; 21; 22; 23]. Various reversible data hiding techniques have been recently proposed to hide confidential data by shifting the histogram of an image [24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38]. In particular, among these techniques, the techniques of [35; 36; 37; 38] are reversible data hiding techniques using a prediction image. In the techniques of [35; 36; 37; 38], a prediction image is generated by predicting pixel values using surface characteristics present in a cover image, and the prediction image is used to embed confidential data in the cover image. [PERSON] et al. proposed the NSAS technique using the histogram of an image [1]. This technique examines the peak and zero points in the histogram of a cover image, shifts the pixels between the points, and inserts confidential data into the pixels corresponding to the peak point. Therefore, the technique has a weakness; the maximum number of bits that can be embedded is limited to the frequency at the peak point in the histogram of the cover image. [PERSON] et al. proposed the adjacent pixel difference (APD) technique [2] that improved the NSAS technique. It is a reversible data hiding technique that embeds confidential data using the histogram of an adjacent pixel difference sequence. In this technique, an adjacent pixel difference sequence composed of the differences between adjacent pixels in the cover image is generated, and then its histogram is generated. As adjacent pixels are generally similar to each other, many elements in the sequence have values close to zero. Therefore, the frequency at the peak point in the histogram of the sequence becomes very large, and the number of data bits that can be hidden in the cover image is greatly increased. This technique has a weakness; the number of data bits that can be embedded in the cover image is limited to the frequency at the peak point in the histogram of the adjacent pixel difference sequence.