# Two-Dimensional Histogram Shifting-Based Reversible Data Hiding for H.264/AVC Video
## 2 HS-based RDH Technique
### Proposed 2D HS-Based RDH Schemes
#### 3.2.1 2D HS Using the \((0,0)\) Coefficient Pairs  
Let \((x,y)\) denote a cover coefficient pair, and the corresponding marked coefficient pair is represented by \((x^{\prime},y^{\prime})\). The proposed 2D HS scheme using the \((0,0)\) coefficient pairs is illustrated in Figure 4. First, all points are divided into several disjoint sets shown below. \[S_{1} =\left\{\left(0,0\right)\right\},\] \[S_{2} =\left\{\left(0,y\right)\mid y>0\ \&\ y\
eq 2\right\},\ \ S_{3}=\left\{\left(-1,1\right)\right\},\ \ S_{4}=\left\{\left(0,y\right)\mid y<0\ \&\ y\
eq-2\right\},\ \ S_{5}=\left\{\left(1,-1\right)\right\},\] \[S_{6} =\left\{\left(x,0\right)\mid x>0\ \&\ x\
eq 2\right\},\ \ S_{7}=\left\{\left(1,1\right)\right\},\ \ S_{8}=\left\{\left(x,0\right)\mid x<0\ \&\ x\
eq-2\right\},\ \ S_{9}=\left\{\left(-1,-1\right)\right\},\] \[S_{10} =\left\{\left(x,y\right)\mid x>0\ \&\ y>0\right\}-S_{7},\ \ S_{11}=\left\{ \left(0,2\right)\right\},\] \[S_{12} =\left\{\left(x,y\right)\mid x<0\ \&\ y>0\right\}-S_{3},\ \ S_{13}=\left\{ \left(-2,0\right)\right\},\] \[S_{14} =\left\{\left(x,y\right)\mid x<0\ \&\ y<0\right\}-S_{9},\ \ S_{15}=\left\{\left(0,-2\right)\right\},\] \[S_{16} =\left\{\left(x,y\right)\mid x>0\ \&\ y<0\right\}-S_{5},\ \ S_{17}=\left\{ \left(2,0\right)\right\}.\]  
Then, the method of embedding data into the coefficient pairs belonging to different sets is described as follows. If \((x,y)\in S_{1}\), the marked coefficient pair will be  
\[(x^{\prime},y^{\prime})= \begin{cases}(x,y)&\text{if }m_{i}m_{i+1}=01,\\ (x+1,y)&\text{if }m_{i}m_{i+1}=10,\\ (x,y-1)&\text{if }m_{i}m_{i+1}=11,\\ (x-1,y)&\text{if }m_{i}m_{i+1}m_{i+2}=000,\\ (x,y+1)&\text{if }m_{i}m_{i+1}m_{i+2}=001.\end{cases}  \tag{13}\]  
If \((x,y)\in S_{2}\cup S_{3}\), the marked coefficient pair will be  
\[(x^{\prime},y^{\prime})= \begin{cases}(x,y+1)&\text{if }m_{i}=0,\\ (x-1,y)&\text{if }m_{i}=1.\end{cases}  \tag{14}\]  
If \((x,y)\in S_{4}\cup S_{5}\), the marked coefficient pair will be  
\[(x^{\prime},y^{\prime})= \begin{cases}(x,y-1)&\text{if }m_{i}=0,\\ (x+1,y)&\text{if }m_{i}=1.\end{cases}  \tag{15}\]  
If \((x,y)\in S_{6}\cup S_{7}\), the marked coefficient pair will be  
\[(x^{\prime},y^{\prime})= \begin{cases}(x+1,y)&\text{if }m_{i}=0\text{ \& }y=0\text{ or }m_{i}=1\text{ \& }y\
eq 0,\\ (x,y+1)&\text{if }m_{i}=1\text{ \& }y=0\text{ or }m_{i}=0\text{ \& }y\
eq 0.\end{cases}  \tag{16}\]  
If \((x,y)\in S_{8}\cup S_{9}\), the marked coefficient pair will be  
\[(x^{\prime},y^{\prime})= \begin{cases}(x-1,y)&\text{if }m_{i}=0\text{ \& }y=0\text{ or }m_{i}=1\text{ \& }y\
eq 0,\\ (x,y-1)&\text{if }m_{i}=1\text{ \& }y=0\text{ or }m_{i}=0\text{ \& }y\
eq 0.\end{cases}  \tag{17}\]  
If \((x,y)\in S_{10}\cup S_{11}\cup S_{12}\cup S_{13}\cup S_{14}\cup S_{15}\cup S_ {16}\cup S_{17}\), any secret data cannot be embedded, so the coefficient pair will be just shifted as  
\[(x^{\prime},y^{\prime})= \begin{cases}(x,y+1)&\text{if }(x,y)\in S_{10}\cup S_{11},\\ (x-1,y)&\text{if }(x,y)\in S_{12}\cup S_{13},\\ (x,y-1)&\text{if }(x,y)\in S_{14}\cup S_{15},\\ (x+1,y)&\text{if }(x,y)\in S_{16}\cup S_{17}.\end{cases}  \tag{18}\]  
Although our method and the method proposed in [34] use the same embedding mode for the \((0,0)\) coefficient pairs, the embedding modes used at other points in our scheme is different from that used in [34]. To evaluate the embedding performance of different schemes, the overall embedding efficiency is defined by  
\[OE=\frac{\sum_{m=1}^{M}r_{m}B_{m}}{\sum_{m=1}^{M}r_{m}V_{m}}, \tag{19}\]  
where \(r_{m}\) is the ratio of points using the embedding mode \(m\) to the total number of points, \(M\) is the number of embedding modes included in a scheme, thus \(\sum_{m=1}^{M}r_{m}=1\). \(B_{m}\) is the number of bits that can be embedded with the embedding mode \(m\), and \(V_{m}\) is the corresponding amount of modification to the DCT coefficient pair. Here, the point shifting without data embedding is considered a special embedding mode that can embed 0 bits.