# Two-Dimensional Histogram Shifting-Based Reversible Data Hiding for H.264/AVC Video
## 2 HS-based RDH Technique  
The one-dimensional (1D) HS-based RDH technique was first developed in [7] for uncompressed images, whose main idea is briefly reviewed here. Firstly, the histogram of pixel values in an image is generated by  
\[h(k)=\#\{x_{i}|x_{i}=k\}, \tag{1}\]  
where \(\#\) denotes the cardinal number of a set, \(k\in[0,255]\cap\mathbb{Z}\), and \(x_{i}\) is a pixel from the image. Then the bins between the peak and zero bins are shifted toward the zero bin by one unit, i.e.,  
\[x_{i}= \begin{cases}x_{i}+1&\text{if }x_{i}\in[k_{p}+1,k_{z}-1],\\ x_{i}&\text{if }x_{i}\
otin[k_{p}+1,k_{z}-1],\end{cases}  \tag{2}\]  
where \(k_{p}\) and \(k_{z}\) denote the pixel values of the peak and zero points of the histogram respectively, and without loss of generality, it is assumed that \(k_{p}<k_{z}\). Finally, the data is embedded into the pixels by  
\[x_{i}= \begin{cases}x_{i}+1&\text{if }x_{i}=k_{p}\ \&\ m_{i}=1,\\ x_{i}&\text{if }x_{i}=k_{p}\ \&\ m_{i}=0,\end{cases}  \tag{3}\]  
where \(m_{i}\) is one bit of secret data to be embedded. The 1D HS-based method is illustrated in Figure 1.  
The classic 2D HS-based RDH technique [19], which is extended from 1D HS-based method, is illustrated in Figure 2. Compared with 1D histogram, 2D histogram is generated by the statistical distribution of value pairs, so the line shown in Figure 1 is changed into a plane, as shown in Figure 2. The point \((x,y)\) in the plane is a value pair composed of different kinds of objects (e.g., prediction errors of pixel values, transform coefficient values) used for data embedding. When the DCT coefficients are used to carry secret data, the value pair is also called a coefficient pair. Thus, the \((0,0)\) DCT coefficient pair, which will be used later in the paper, denotes a pair of DCT coefficients with both values 0. There are various ways of pairing objects. For example, two consecutive DCT coefficients in a block or two DCT coefficients from adjacent blocks with the same frequency can be paired. Each arrow in Figure 2 indicates the possible modification of the value pairs. The number of arrows ending at a certain point can be called the in-degree of the point, and the number of arrows starting with a point can be called its out-degree. Generally, the amount of the modification to a value pair will be different when the value pair is modified along different directions. For instance, when a value pair \((x,y)=(1,0)\) is modified to \((2,1)\) or \((2,0)\) when \(m_{i}=0\) or \(m_{i}=1\), the corresponding amount of the modification to \((1,0)\) is 2 or 1, respectively. For ease of discussion, the modification method of a point with a given out-degree is referred to as the embedding mode of the point, and the combination of different embedding modes is called an embedding strategy in the rest of this paper. Since each point can be modified with many different embedding modes, there are various embedding strategies to design a 2D HS-based scheme, which will result in different embedding efficiency. High embedding efficiency means that more data can be embedded per unit modification. For compressed media, the classic 2D HS-based method may not be efficient enough. The reason is that, unlike pixels in uncompressed images, the objects used for data embedding in the compressed domain need to be encoded. For those commonly used objects, e.g., DCT coefficients and MVs, the results of entropy coding are sensitive to their values. For example, entropy coding of DCT coefficients in H.264/AVC video is related to the coefficient values of both current block and neighboring blocks. In addition, the distribution of zero values also has a great impact on the efficiency of entropy encoding. To improve embedding efficiency, several 2D HS-based RDH schemes have recently been proposed for JPEG images [29] and H.264/AVC videos [33; 34; 37], which will be analyzed in the following section. Figure 1: Illustration of 1D HS-based method. Figure 2: Classic 2D HS-based method.