Two-dimensional histogram modification based reversible data hiding using motion vector for H.264

Abstract

Histogram modification (HM) is an efficient algorithm for reversible data hiding into H.264 video, motion vector based methods have been applied to HM. In this paper, we present a special strategy of reversible data hiding using motion vector based on two-dimensional histogram modification. Firstly, the two components of a motion vector will compose an embedding pair. The values of embedding pairs are classified into 17 non-intersect sets. Then, according to the set that the embedding pair belongs to, we can embed data into motion vectors by modifying the value of embedding pair. Experimental results verify that the embedding capacity is increased by two times compared with the previous algorithm, and the PSNR declines about 5%. The reversibility of the algorithm is also studied, three rules are presented to judge the reversibility of an algorithm directly, and the rules are suitable for other histogram modification based methods.

1 Introduction

Reversible data hiding (RDH) means the original medium can be completely recovered after the hidden data has been extracted [1]. For watermark, robustness is more important, Zhang et al. [18] proposed a robust image steganography that the message can be correctly transmitted even after JPEG compression, but in the fields such as medical, military and legal ones, the distortion of images and videos is sometimes unacceptable, that is, the irreversible loss of carrier is not allowed [2]. RDH can solve this problem properly and the information can be extracted with the carrier recovered completely. The first RDH method was proposed for image authentication [3]. At present, difference expansion (DE) and histogram modification (HM) are two mainly algorithms used for RDH in images. Compared with image, videos have lots of advantages. Higher quality allows a larger distortion, and more redundancy means a higher embedding capacity. Since H.264 compression standard has become the mainstream video codec, it is necessary to find ways to apply RDH methods into H.264 video.

Tian proposed DE for RDH into images [13]. The difference between two pixels is extended to embed one bit with their average value keeps intact, and the process is reversible. A novel RDH algorithm based on two-dimensional histogram modification is proposed [19], in this method, two quantified DCT (QDCT) coefficients are randomly selected from a 4 × 4 block, the two coefficients will form a pair, according to the set that the pair belongs to, the value of the pair is modified to embed data, and the algorithm possesses a large embedding capacity.

HM algorithm has drawn attention of researchers. In order to decrease the distortion, our group introduces a parameter K stands for the reference frame interval [10]. By modifying K, a large embedding capacity and good visual quality can be both got. The data is embedded into the horizontal components or the vertical ones of motion vectors (MV) by modifying the histogram, however when the histogram is modified once, only one-bit data can be embedded, which limits the embedding capacity.

In this paper, we present a novel algorithm based on two-dimensional histogram modification of MVs. The vertical and horizontal component of a MV constitute an embedding pair, and the values of embedding pairs are classified into 17 non-intersect sets. By modifying the two components of a motion vector simultaneously, more data can be embedded at one time, and the distortion performance is acceptable.

2 Preliminaries

2.1 Motion compensation and motion vector

H.264 compression standard is efficient in video coding, which supports multiple blocks from 16 × 16 to 4 × 4. Under the 8 × 8 mode, the blocks can be divided into8 × 4, 4 × 8, 4 × 4 sub-blocks, as shown in Fig. 1 [11]. The blocks are estimated in 1/4-pixel precision, and it means H.264 has more MVs compared with previous compression standards such as MPEG-2 etc. Therefore, MV is an ideal carrier for data embedding. Lin et al. [6] proposed an algorithm that MVs are divided into different groups, and some of them are chosen to embed watermark. MVs are suitable for steganography as well. In Song’s algorithm [12], researchers presented a reversible video steganography scheme to hide information into the motion vector of each block for 3D MVC videos. MVs can also be employed to achieve error concealment [15].

Fig. 1

Partition of blocks

Discrete Cosine Transform(DCT) is another key step of H.264 standard. DCT employs an integer transformation based on 4 × 4 sub-blocks,DCT blocks become QDCT blocks after quantification, and many RDH algorithms are implemented on QDCT coefficients [7], in H.264/AVC, treat the to-be embedded data with BCH syndrome code, and then embed the encoded data into the QDCT coefficients, in this way, robustness can be improved.

2.2 Previous algorithm

H.264 possesses a higher prediction accuracy, it means the histogram of H.264 video is more smooth than previous standard, and there are more 1 and − 1 points in H.264’s motion vector histogram. Our group proposed an algorithm (MVHM) by modifying±1 points [10]:

$$ mv{x}_{ij}^{\prime }=\Big\{{\displaystyle \begin{array}{ll} mv{x}_{ij}& if\left( mv{x}_{ij}=0\ or \operatorname {mod}\left(i,K\right)=0\right)\\ {}\frac{4 mv{x}_{ij}+\mathit{\operatorname{sign}}\left( mv{x}_{ij}\right)}{4}& if\left(|4 mv{x}_{ij}|>1\ and\ Key(i)=1\right)\\ {}\frac{4 mv{x}_{ij}+\mathit{\operatorname{sign}}\left( mv{x}_{ij}\right)b}{4}& if\left(|4 mv{x}_{ij}|=1\ and\ Key(i)=1\right)\end{array}} $$

(1)

$$ mv{y}_{ij}^{\prime }=\Big\{{\displaystyle \begin{array}{ll} mv{y}_{ij}& if\left( mv{y}_{ij}=0\ or \operatorname {mod}\left(i,K\right)=0\right)\\ {}\frac{4 mv{y}_{ij}+\mathit{\operatorname{sign}}\left( mv{y}_{ij}\right)}{4}& if\left(|4 mv{y}_{ij}|>1\ and\ Key(i)=0\right)\\ {}\frac{4 mv{y}_{ij}+\mathit{\operatorname{sign}}\left( mv{y}_{ij}\right)b}{4}& if\left(|4 mv{y}_{ij}|=1\ and\ Key(i)=0\right)\end{array}} $$

(2)

where mvx and mvy are the horizontal and vertical components of the motion vector, respectively, the mvx^′ and mvy^′ are the component after modified, respectively. Then mv_ij is the j-th motion vector of the i-th frame. K is a parameter that used to control the frame interval, and i is the number of current frame. When mod(i, K) = 0, it means that frame f_i is the reference frame of f_i + 1 to f_i + k. b is the to-be embedded data bit. Key is a random binary sequence, and the length is equal to the number of frames that to be embedded, the value of Key(i) is used to determine which component of motion vector is employed for data embedding.

The data extracting algorithm:

$$ {b}^{\prime }=\Big\{{\displaystyle \begin{array}{ll}0& \begin{array}{l} if\left(\right(\left( Key(i)=1\ and\ |4 mv{x}^{\prime }|=1\right)\\ {} or\ \left( Key(i)=0\ and\ |4 mv{y}^{\prime }|=1\right)\Big)\\ {} and\ \left(\mathit{\operatorname{mod}}\left(i,K\right)\ne 0\right)\Big)\end{array}\\ {}1& \begin{array}{l} if\left(\right(\left( Key(i)=1\ and\ |4 mv{x}^{\prime }|=2\right)\\ {} or\ \left( Key(i)=0\ and\ |4 mv{y}^{\prime }|=2\right)\Big)\\ {} and\ \left(\mathit{\operatorname{mod}}\left(i,K\right)\ne 0\right)\Big)\end{array}\end{array}} $$

(3)

As the algorithm employs the method proposed by Ni et al. [9], the embedding process is reversible. The video recovery algorithm is as follows:

$$ mv{x}_{ij}^{{\prime\prime} }=\Big\{{\displaystyle \begin{array}{ll} mv{x}_{ij}^{\prime }& \begin{array}{l} if\Big( mv{x}_{ij}^{\prime }=0\ or\ Key(i)=0\\ {} or\ \mathit{\operatorname{mod}}\left(i,K\right)=0\ or\mid 4 mv{x}_{ij}^{\prime}\mid =1\Big)\end{array}\\ {}\frac{4 mv{x}_{ij}^{\prime }-\mathit{\operatorname{sign}}\left( mv{x}_{ij}^{\prime}\right)}{4}& \begin{array}{l} if\Big(\mid 4 mv{x}_{ij}^{\prime}\mid \ge 2\\ {} and\ Key(i)=1\Big)\end{array}\end{array}} $$

(4)

$$ mv{y}_{ij}^{{\prime\prime} }=\Big\{{\displaystyle \begin{array}{ll} mv{y}_{ij}^{\prime }& \begin{array}{l} if\Big( mv{y}_{ij}^{\prime }=0\ or\ Key(i)=1\\ {} or\ \mathit{\operatorname{mod}}\left(i,K\right)=0\ or\mid 4 mv{y}_{ij}^{\prime}\mid =1\Big)\end{array}\\ {}\frac{4 mv{y}_{ij}^{\prime }-\mathit{\operatorname{sign}}\left( mv{y}_{ij}^{\prime}\right)}{4}& \begin{array}{l} if\Big(\mid 4 mv{y}_{ij}^{\prime}\mid \ge 2\\ {} and\ Key(i)=0\Big)\end{array}\end{array}} $$

(5)

Obviously, the embedding capacity of the previous algorithm is depended on the number of 1 and − 1 points, and the distortion is limited in K frames.

3 Proposed algorithm

From the previous algorithm, we can conclude that only one-bit data can be embedded when the motion vector changed once, which limits the capacity. In order to improve the embedding efficiency, we present a novel algorithm based on two- dimensional histogram modification (2DMVHM) in this paper, shown in Fig. 2. m_t is the t-th data bit to be embedded, m_t + 1 is the (t + 1)-th data bit to be embedded.

Fig. 2

embedding algorithm of 2DMVHM

The algorithm can be described as follows:

• (1) Encode the video sequence by H.264 standard, in the process of coding, select the motion vectors used for data embedding.

• (2) For every selected motion vector, get the horizontal and vertical component, denoted as (mvx, mvy), which makes up an embedding pair, before embedding, all the pairs would be divided into 17 nonintersecting sets, and each set has an embedding algorithm.

• (3) According to which set the embedding pair belongs to, the corresponding embedding algorithm is used to modify the value of the pair, and data would be embedded at the same time.

3.1 Sets classification

As shown in Fig. 2, all the points in the figure would be divided into 17 nonintersecting sets, the sets are defined as follows:

$$ {\displaystyle \begin{array}{l}{A}_1=\left\{\left(1,0\right)\right\}\\ {}{A}_2=\left\{\left(0,1\right)\right\}\\ {}{A}_3=\left\{\left(-1,0\right)\right\}\\ {}{A}_4=\left\{\left(0,-1\right)\right\}\\ {}{A}_5=\left\{\left({Y}_{S1},0\right)|{Y}_{S1}>1\right\}\\ {}{A}_6=\left\{\left({Y}_{S1},0\right)|{Y}_{S1}<-1\right\}\\ {}{A}_7=\left\{\left({Y}_{S1},1\right)|{Y}_{S1}\ge 1\right\}\\ {}{A}_8=\left\{\left({Y}_{S1},1\right)|{Y}_{S1}\le -1\right\}\\ {}{A}_9=\left\{\left({Y}_{S1},-1\right)|{Y}_{S1}\le -1\right\}\end{array}}\kern0.5em {\displaystyle \begin{array}{l}{A}_{10}=\left\{\left({Y}_{S1},-1\right)|{Y}_{S1}\ge 1\right\}\\ {}{A}_{11}=\left\{\left(0,{Y}_{S2}\right)|{Y}_{S2}>1\right\}\\ {}{A}_{12}=\left\{\left(0,{Y}_{S2}\right)|{Y}_{S2}<-1\right\}\\ {}{A}_{13}=\left\{\left({Y}_{S1},{Y}_{S2}\right)|{Y}_{S1}\ge 1,{Y}_{S2}\ge 2\right\}\\ {}{A}_{14}=\left\{\left({Y}_{S1},{Y}_{S2}\right)|{Y}_{S1}\le -1,{Y}_{S2}\ge 2\right\}\\ {}{A}_{15}=\left\{\left({Y}_{S1},{Y}_{S2}\right)|{Y}_{S1}\le -1,{Y}_{S2}\le -2\right\}\\ {}{A}_{16}=\left\{\left({Y}_{S1},{Y}_{S2}\right)|{Y}_{S1}\ge 1,{Y}_{S2}\le -2\right\}\\ {}{A}_{17}=\left\{\left(0,0\right)\right\}\end{array}} $$

Among them, (Y_S1, Y_S2) is four times of mvx and mvy, respectively. Because the accuracy of motion estimation is 1/4 pixel in H.264, and in the below text, $\left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)$ is four times of mvx^′ and mvy^′, respectively.

3.2 Embedding algorithm

The presented algorithm can be illustrated by Fig. 2. The details of embedding procedure are described as follows:

• (1) if (Y_S1, Y_S2) ∈ A₁, the marked components denoted as $\left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)$ will be

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=00\\ {}\left({Y}_{S1}+1,{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1},{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=10\\ {}\left({Y}_{S1},{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=11\end{array}} $$

(6)

• (2) if (Y_S1, Y_S2) ∈ A₂, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=00\\ {}\left({Y}_{S1}+1,{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1},{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=10\\ {}\left({Y}_{S1}-1,{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=11\end{array}} $$

(7)

• (3) if (Y_S1, Y_S2) ∈ A₃, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=00\\ {}\left({Y}_{S1}-1,{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1},{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=10\\ {}\left({Y}_{S1},{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=11\end{array}} $$

(8)

• (4) if (Y_S1, Y_S2) ∈ A₄, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}\right)& if\ {m}_t{m}_{t+1}=00\\ {}\left({Y}_{S1}+1,{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1},{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=10\\ {}\left({Y}_{S1}-1,{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=11\end{array}} $$

(9)

• (5) if (Y_S1, Y_S2) ∈ A₇, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}+1,{Y}_{S2}\right)& if\ {m}_t=0\\ {}\left({Y}_{S1}+1,{Y}_{S2}+1\right)& if\ {m}_t=1\end{array}} $$

(10)

• (6) if (Y_S1, Y_S2) ∈ A₈, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}-1,{Y}_{S2}\right)& if\ {m}_t=0\\ {}\left({Y}_{S1}-1,{Y}_{S2}+1\right)& if\ {m}_t=1\end{array}} $$

(11)

• (7) if (Y_S1, Y_S2) ∈ A₉, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}-1,{Y}_{S2}\right)& if\ {m}_t=0\\ {}\left({Y}_{S1}-1,{Y}_{S2}-1\right)& if\ {m}_t=1\end{array}} $$

(12)

• (8) if (Y_S1, Y_S2) ∈ A₁₀, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}+1,{Y}_{S2}\right)& if\ {m}_t=0\\ {}\left({Y}_{S1}+1,{Y}_{S2}-1\right)& if\ {m}_t=1\end{array}} $$

(13)

• (9) if (Y_S1, Y_S2) ∈ A₁₁, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}+1\right)& if\ {m}_t=1\\ {}\left({Y}_{S1}+1,{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1}-1,{Y}_{S2}+1\right)& if\ {m}_t{m}_{t+1}=00\end{array}} $$

(14)

• (10) if (Y_S1, Y_S2) ∈ A₁₂, then

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1},{Y}_{S2}-1\right)& if\ {m}_t=1\\ {}\left({Y}_{S1}+1,{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=01\\ {}\left({Y}_{S1}-1,{Y}_{S2}-1\right)& if\ {m}_t{m}_{t+1}=00\end{array}} $$

(15)

• (11) if (Y_S1, Y_S2) belongs to A₅, A₆, A₁₃, A₁₄, A₁₅, A₁₆, no information is embedded into the MVs, and $\left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)$ will be

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}+1,{Y}_{S2}\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_5\\ {}\left({Y}_{S1}-1,{Y}_{S2}\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_6\\ {}\left({Y}_{S1}+1,{Y}_{S2}+1\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_{13}\\ {}\left({Y}_{S1}-1,{Y}_{S2}+1\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_{14}\\ {}\left({Y}_{S1}-1,{Y}_{S2}-1\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_{15}\\ {}\left({Y}_{S1}+1,{Y}_{S2}-1\right)& if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_{16}\end{array}} $$

(16)

• (12) if (Y_S1, Y_S2) ∈ A₁₇, then $\left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)$ will be

$$ \left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime}\right)=\left({Y}_{S1},{Y}_{S2}\right)\kern0.5em if\ \left({Y}_{S1},{Y}_{S2}\right)\in {A}_{17} $$

(17)

After modified, the values of the pair will belong to a new set, whereas, from Fig. 2, we can see that the in-degree of each point (except for (0,0)) is 1, and it means after modified, every marked point comes from the unique point. That is to say, the algorithm is reversible, the extracting algorithm is the reverse process of Fig. 2.

4 Experimental results and analysis

4.1 Data embedding

The original video can be generated by encoding YUV video with H.264 standard, and we take 8 video sequences for experiments. We will take 150 frames from each video for data embedding.

In the experiment, we will compare the previous algorithm MVHM with presented algorithm 2DMVHM in the aspects of embedding capacity and PSNR. The comprehensive experimental results are shown in Table 1.

Table 1 comprehensive experimental results

From Table 1, we can see that different video sequence provides different embedding capacity, and the capacity will rise with the increase of K, whereas, the PSNR is decreasing as K increases, that’s because when the frame interval is larger, more frames will be embedded information, and the distortion will accumulate more severely.

Compared with the previous algorithm, the method proposed in this paper possesses a higher embedding capacity, and the distortion performance is acceptable. The reasons are as follows:(1) for the previous algorithm, under the control of Key(i), only one kind of components will be selected to embed data, but in the new method, mvx and mvy are modified together, and when the pair is changed once, 2 bits can be embedded at most, and due to the introduction of two-dimension, some original points that are unable to embed information (in the previous method) can be employed to hide data (in the new method), like (1,0). (2) for the distortion performance of 2DMVHM method, although the two components of MVs are modified together, the results turn out to be only one of them would be changed at most time. Take (1, 0) for instance, after modified, the result would be one of the four, (1, 0), (2, 0), (1, 1), (1, −1), and only one component would be changed at a time.

In consideration of sometimes PSNR cannot reflect the distortion completely, we conducted additional experiments to figure out the bitrate increase introduced by the proposed algorithm. As shown in Table 2, under different K, the bitrate increase differs from each other. We can see that under the same K, 2DMVHM algorithm suffers a larger bitrate increase compared with MVHM. After the value of MV being modified, the residual between the reference block and current block tends to become larger, it will cost more bits to encode the residual. On the other hand, in the experiment, the first frame is I-mode frame, and the subsequent frames are all P-mode, if more I-mode frames are encoded, the bitrate variation will be decreased, but the embedding capacity will be decreased as well.

Table 2 comparison of bitrate increase

4.2 Data extracting and video recovery

By decoding the data embedded video, receiver can get all the motion vectors and different marked motion vectors have different extracting algorithms, data can be extracted by using the corresponding algorithm, at the same time, the video can be recovered completely. The data extracting flow chart is shown in Fig. 3.

Fig. 3

Data extracting and video recovered process

As the data extracting is the reverse process of algorithm shown in Fig. 2, here, we’ll take A₁ for instance:

$$ data=\Big\{{\displaystyle \begin{array}{ll}\left(0,0\right)& if\ \left({Y}_{S1}^{\prime }=1\ and\ {Y}_{S2}^{\prime }=0\right)\\ {}\left(0,1\right)& if\ \left({Y}_{S1}^{\prime }=2\ and\ {Y}_{S2}^{\prime }=0\right)\\ {}\left(1,0\right)& if\ \left({Y}_{S1}^{\prime }=1\ and\ {Y}_{S2}^{\prime }=1\right)\\ {}\left(1,1\right)& if\ \left({Y}_{S1}^{\prime }=1\ and\ {Y}_{S2}^{\prime }=-1\right)\end{array}} $$

(18)

In this equation, data is the extracted information.

The video will be recovered when data is extracted, we’ll take A₁₁ for instance:

$$ \left({Y}_{S1}^{{\prime\prime} },{Y}_{S2}^{{\prime\prime}}\right)=\Big\{{\displaystyle \begin{array}{ll}\left({Y}_{S1}^{\prime },{Y}_{S2}^{\prime }-1\right)& if\ \left({Y}_{S1}^{\prime }=0\ and\ {Y}_{S2}^{\prime }>2\right)\\ {}\left({Y}_{S1}^{\prime }-1,{Y}_{S2}^{\prime }-1\right)& if\ \left({Y}_{S1}^{\prime }=1\ and\ {Y}_{S2}^{\prime }>2\right)\\ {}\left({Y}_{S1}^{\prime }+1,{Y}_{S2}^{\prime }-1\right)& if\ \left({Y}_{S1}^{\prime }=-1\ and\ {Y}_{S2}^{\prime }>2\right)\end{array}} $$

(19)

In the equation, $\left({Y}_{S1}^{{\prime\prime} },{Y}_{S2}^{{\prime\prime}}\right)$ is four times of recovered mvx and mvy, respectively.

By this way, the data can be extracted while the video will be recovered. For the extracting experiment, we embed data into 150 frames of the video “foreman.qcif”, and let K is 2, then decode the sequence with different Ks, in the experiments, we would take the original video as comparison. The result is shown in Fig. 4. From the figure we can conclude that the data-embedded video could be recovered only when K is 2, with incorrect K, the quality of video is declining seriously, that’s because data embedding influences the quality of video greatly [16, 17].

Fig. 4

The results of video recovering

In the experiments, the video is fully embedded, but in the practical application, there won’t be so much information to be embedded, in order to improve the quality of data-embedded video, we can introduce a parameter Key, which is a random binary sequence used to decide whether the data would be embedded into the current frame or not, that is to say, if Key(i) = 1, the current frame would be used to embed data, otherwise this frame will be kept intact. By this way, the distortion will be decreased ulteriorly.

4.3 Analysis of reversibility

From the data extracting experiments, we can see that the video can be recovered completely after data being extracted. In most instances, the reversibility of an algorithm cannot be ensured until the data extracting experiments have been conducted. By studying the diagram of embedding algorithm shown in Fig. 2, from the perspective of in-degree and out-degree, we presented some rules that could be used to judge the reversibility of an algorithm directly:

• (1) In-degree of all the points is 1.

• (2) Out-degree of all the points is N.

• (3) Where there is an in-degree, there is an out-degree.

When the diagram of an algorithm satisfies the above rules, the algorithm must be reversible. We will take Fig. 1 for instance. Except for the point (0,0), the in-degree of the rest points is 1, it means after modified, we can still find out the original position that the points belong to. The number of out-degree directly influences the embedding capacity of a point. After modified, the points would be changed to a new position, to ensure the reversibility, the modified points must be set apart from the original points that in the same position. It is obviously that the proposed algorithm satisfies all the above rules, the algorithm is reversible in theory, from Fig. 4, we can see that the video can be recovered completely by using the correct parameter K, the PSNR of recovered video and the original video are coincident, it means the proposed method is reversible not only in theory, but also in experiment. There are still many characters can be inferred from the diagram, the relevant research will be implemented in our future work.

5 Conclusion

In this paper, we proposed a novel two-dimensional histogram modification based RDH for H.264, compared with the previous algorithm, the proposed method can make full use of relevance between the two components of MV, and embedding capacity is enlarged greatly, at the same time, the distortion performance is acceptable. However, there is still a large space to improve the performance of the proposed algorithm, and the method could also be extended to multi-dimension in theory.

As the cloud computing technology developing greatly, the security problem of cloud storage has drawn the public attention [5], it is significant to apply RDH algorithms into encryption domain to meet the demands of cloud storage. With the developing of steganalysis [8, 14, 20], the conventional data hiding algorithms are faced with severe challenges, coverless information hiding will provide a promising solution [4]. In our future work, we would like to study the common characters that RDH algorithms share, and try to build a theoretical base for the design of RDH methods, then we would try to design a RDH method suitable for encrypted video, and the coverless information hiding based on video will also be studied.