## 2 Descriptions of Conventional Histogram-Based Reversible Data Hiding  
The concept of data hiding is to embed secret information relating to the copyright owner into original multimedia content, depicted in Figure 1. For reversible data hiding, the secret to be hidden, \(S\), is first embedded into the cover image \(\mathbf{X}\). Later on, at the decoder, by performing the reverse of the information embedding process, both the embedded secret and the recovered image, which is exactly the same as the cover image, should be extracted. The main challenge of reversible data hiding is to develop an algorithm that is reversible, that is, all the inputs to the encoder in Figure 1(a), including the cover image \(\mathbf{X}\) and hidden secret \(S\), must be perfectly extracted at the decoder after delivery of the marked image \(\mathbf{X}^{\prime}\). After completing the extraction procedure, the outputs of the extractor in Figure 1(b) must be identical to the inputs of encoder in Figure 1(a), or \(\widetilde{\mathbf{X}}=\mathbf{X}\) and \(\widetilde{S}=S\).  
For the implementation of reversible data hiding algorithms, reversible data hiding can be categorized into three major branches. The first one is by modifying the histogram of original image for embedding the user-defined information [8], the second one is called the difference expansion (DE) scheme [9], and the third one is by the replacement of the least significant bits (LSB) of the original image. Characteristics of the three schemes are briefly discussed as follows.  
For the histogram-based scheme to be addressed shortly in Section 2.1, for making data embedding possible, only a portion of the histogram needs to be moved. It implies that no calculation is necessary in the data embedding process. Due to the ease of implementation, we will focus on the histogram-based scheme in this paper.  
For the DE scheme, the average and difference values between two consecutive pixels need to be calculated. Also, for data embedding, multiplication of the difference value is required, and that's the meaning of \"difference expansion\" originated. Besides, the quality of the output image can hardly be guaranteed with the DE scheme even though a large embedding capacity can be expected. Most important of all, some pixel pairs may be unsuitable for making data hiding possible because the difference between two consecutive pixels may be large, which would cause an overflow problem after embedding with difference expansion. These unsuitable positions for data hiding, called the location map, need to be recorded for correct extraction of data at the decoder. Location map should be delivered to the decoder for data extraction and original recovery, which is regarded as the side information for reversible data hiding. Based on the characteristics of original images, the size of location map may grow to some considerable amount, which would limit the performances with the DE scheme.  
Finally, for the LSB-replacement scheme, it is one of the simplest schemes for reversible data hiding. By hiding the secret data into the LSB of the original image, reversible data hiding can be completed. Because papers focusing on this topic were a bit outdated, mostly published around ten years ago, we omit the comparisons with this scheme.  
Due to the ease of implementation, we concentrate on the histogram-based scheme in this paper to realize the application of our method.