2.1.

Impact on Data Size

Most natural (i.e., not artificial) images have a great spatial redundancy. Therefore, the orthogonal transformations are performed to reduce the effects of the redundancy. As a result, the values of the AC coefficients have the tendency of a Laplacian distribution where the location parameter $\mu =0$, as shown in Fig. 1.^25,26 Utilizing the characteristics of the Laplacian distribution, the qTCs will then be coded by applying two entropy coding methods: context adaptive variable length coding (CAVLC) or context adaptive binary arithmetic coding (CABAC). MPEG-2 supports only CAVLC, HEVC supports only CABAC while H.264/AVC supports both. In general, entropy coding methods distribute shorter code to more frequent data.

Fig. 1

Laplacian distribution of the AC coefficients.

In the case of CAVLC, qTCs are broken down into level values and zero run-length values before applying CAVLC. Afterwards, the level values and the zero run-length values are coded (as run-level pairs in MPEG-2; separately in H.264/AVC) using the VLC tables. According to the tables, as long as the amount of the zero coefficients in one block remains unchanged, the data size will decrease when the absolute values of the AC coefficients decrease.

In the case of CABAC, only the levels and the positions of the non-zero AC coefficients are coded. Those values are broken down into several syntaxes and then binarized and coded. The same as in the case of CAVLC, as long as the amount of the zero coefficients in one block remains unchanged, the data size will decrease when the absolute values of the AC coefficients decrease.

Consequently, in order to decrease the data size, it is reasonable to decrease the absolute values of the non-zero AC coefficients without reducing the amount of zero AC coefficients.

2.2.

Classical LSB Replacement Technique

For one piece of data, its bit plane can be arranged in a from-most-to-least significant order, and the last bit in that order is expressed as an LSB. For example, the rightmost bit of an eight-bit binary number is its LSB. In the classical LSB replacement technique, the LSB of the target of data hiding will be replaced with one bit of additional data, and this process may cause the original value of the target to change by one. The embedded one bit of data can be extracted by directly referring to the LSB of the target. An example of the classical LSB replacement technique is shown in Fig. 2.

Fig. 2

Example of classical LSB replacement technique.

2.3.

Modulo Addition Technique

For one piece of integer data, the value of it could be expressed as $V$. The process embedding one bit of additional data, which has a value of $A$ will change $V$ to $V_e$ as follows:

The embedded data bit $A$ could be extracted as follows:

In fact, the modulo addition technique can be considered as a variant of the classical LSB replacement technique, in particular the two techniques are sometimes totally the same depending on the representation method of the bit plane of negative numbers.

According to Sec. 2.1, in MPEG-2, H.264/AVC, and HEVC formats, the same as in some other image and video formats using orthogonal transformations, such as JPEG, turning an AC coefficient with a value of 0 into a non-zero value will directly increase the data size. Obviously, the classical LSB replacement technique and the modulo addition technique will inevitably increase the number of non-zero AC coefficients. In addition, according to Eq. (1), if $V$ is positive and is a multiple of 2, the absolute value of $V_e$ will be greater than that of $V$ when $A=1$.

Those features pose a risk of massive data size increase, which is undesirable in most scenarios of data hiding, e.g., in the case that the remaining capacity of the video disc is insufficient. This technique will be expressed as “MA” since then.

2.4.

Modified Modulo Addition Technique

As a modified version of the modulo addition technique, an approach has been proposed before.²⁷ In that approach, in order to avoid the risk of increasing the absolute value of an AC coefficient, the algorithm of embedding was modified as follows:

The embedded data bit $A$ could be extracted with Eq. (2) as well.

This technique avoids the risk to increase the absolute value of a non-zero AC coefficient. On the other hand, it changes the value of some AC coefficients from 0 to 1. As a result, the data size of the video may increase after data hiding process. This technique will be expressed as “mMA” since then.

The ideal positions to embed additional data in a block have been studied before.²⁸ The qTCs of a $8\times 8$ block could be divided into three regions, which are $F_L$ (low frequencies), $F_M$ (medium frequencies), and $F_H$ (high frequencies) as shown in Fig. 3. The band of frequencies suitable for embedding purpose is $F_M$.²⁸ However, the mMA technique performs data hiding mainly in $F_L$. In order to develop this technique, AC coefficients in $F_M$ should be chosen for embedding when the payload is slight.

Fig. 3

Various frequency regions in a $8\times 8$ block.

2.5.

Other Related Techniques

Some other data hiding techniques proposed for compressed images and videos have also been proposed.^29–32 Mobasseri et al. proposed a data hiding technique for MPEG-2 videos using VLC mapping,²⁹ which will not increase the data size of the videos. However, it only supports CAVLC and but also requires detection process beforehand. In addition, the maximum payload size depends on the cover video. Chaumont et al. proposed a DCT-based data hiding technique that spreads the payload data into a group of DCT coefficients.³⁰ The technique can realize a better image quality, but it also leads to a data size increase. Hartung et al. can embed additional data into MPEG-2 videos without data size increase,³¹ yet it has a risk of losing the additional data because it embeds the additional data into the inverse quantized DCT coefficients and quantize them again (the quantization process is lossy). Those techniques are effective respectively in some scenarios, but any one of them has obvious defects in other scenarios, especially in the cases of data hiding into capacity-limited multimedia storages.

F4, the base of F5,³² is a technique that embeds data into nonzero AC coefficients of cover data while reducing the cover data size. However, this technique inevitably turns some 1 and $-1$ AC coefficients into zeros, thus in order to acquire the embedded data, a unique key for each cover data is needed to be produced to record which zeros are unchanged, which are changed from 1 and which are changed from −1. This key has to be merged with any other keys for data extraction of each cover data and the key-sharing is costly in most data hiding situations. F5 is an improved version of F4 and also has this characteristic.

3.1.

Overview

In MPEG-2, H.264/AVC, and HEVC, frames (pictures) are classified as I (intra) pictures, P (predictive) pictures, and B (bidirectionally predictive) pictures. Each frame is divided into blocks and the blocks are classified roughly as intra-blocks and inter-blocks of luminance and chrominance. Orthogonal transformations and quantization are then performed within each block and qTCs are acquired. Because inter-blocks are basically predicted from intra-blocks, the degradation of the intra-blocks will be propagated to inter-blocks and accumulated.³³ At the same time, human eyes are more sensitive to direct current (DC) coefficients than alternating current (AC) coefficients. Thus, it is conceivable that AC ingredients of qTCs in intra-blocks are proper targets of data hiding process. The flowcharts of the proposed processes are shown in Fig. 4.

Fig. 4

Flowcharts of the proposed processes: (a) embedding and (b) extracting.

3.2.

Details of the Proposed Technique

In this section, the proposed polarized LSB replacement technique will be explained and discussed.

What we have already discussed is that the video data size may increase after data hiding process in MA and mMA, and key-sharing is costly in F4. Here, we propose a novel technique, polarized LSB replacement, to avoid data size increase and key-sharing, which will be expressed as “PLSB-r” since then. Before the algorithm is explained, a partial lookup table including several original qTCs and the corresponding modified qTCs for MA, mMA, and PLSB-r is shown as Table 1. The changes of the qTC values are shown in Fig. 5: where the red arrows refer to the changes which increase the absolute value of qTCs, green arrows for changes which decrease the absolute value of qTCs, and white ones for no change of the absolute value. From Table 1 and Fig. 5, we can conclude that different from MA and mMA, the proposed technique never increases the absolute value of any qTC. Further, as long as any qTC which has a value greater than 1 or less than −1 exists (this condition is basically satisfied in all natural images and videos with sufficient quality), the video data size decreases due to the decrease of the absolute value of those qTCs.

Table 1

Modified qTC lookup table.

Fig. 5

Changes of qTC values: (a) MA, (b) mMA, (c) F4, and (d) PLSB-r.

The algorithm of the proposed PLSB-r technique is explained below. First, only in the cases where $V\ne 0$, $V_e$ is acquired as follows:

In the proposed technique, the sign of a qTC with a value of 1 or $-1$ may invert, i.e., $-1$ becomes 1; 1 becomes $-1$, and the parity of the positive modified qTCs and negative modified qTCs conflict when the same data bit is embedded. The histogram for AC coefficients of cover data remains symmetrical and nearly remains a Laplacian distribution, therefore whether the cover data carry hidden data is difficult to detect by attackers. These characteristics make the proposed technique totally different from conventional LSB replacement and modulo addition techniques, in which the parity of the positive modified qTCs and negative modified qTCs are generally the same. Due to that feature of the proposed technique, although the robustness of the proposed technique is relatively weak, it is more effective to use it in steganography situations, in which the lack of detectability is rather important, or enrichment situations, in which the robustness can be disrespected to a certain extent.

The time-complexity of both the data hiding process and the data extraction process is $O(n)$. The processing time of the proposed technique is generally negligible, which is $<1/100$ of the video coding or decoding time in our experiments. Thus, the proposed technique is suitable for real-time situations where an information timeline is important. The scheme of the proposed technique is simple so that it can be combined with other data hiding techniques that enhance security and other aspects.

As defect of the proposed technique, the maximum payload will be less than MA and mMA because embedding process is only performed to non-zero qTCs, and the quality will be slightly worse than F4 because the change of the absolute value of 1 and $-1$ AC coefficients is greater.

As shown in Table 1, when $n=1$, the absolute value of an AC coefficient will never increase after the embedding process is performed.

4.1.

Overview

To verify the effectiveness of the proposed technique, we conducted several experiments with the MPEG-2 format.

In the experiments, the 15 videos we used were uncompressed raw videos in YUV format.³⁴ The first frames of the experimental videos are shown in Fig. 6. The 15 raw videos were compressed to common DVD and BD formats that are also generally used in the videos of online services with the specifications shown in Table 2, respectively. The compressed videos with no data embedded will be represented as baseline videos since then. In order to compare the videos with data embedded and the baseline videos objectively, fixed quantization parameter (QP) values are used to keep the coding process the same for the comparison objects. The QP values of different videos vary in order to keep the bit rates similar for different videos as shown in Table 3. The bit rates of the baseline videos and the average of them are shown in Fig. 7. The additional data to be embedded are a randomly generated bit-sequence $S$ and all experiments use the same $S$.

Fig. 6

First frames of the experimental videos. Horizontally from top left: a, aspen; co, controlled burn; cr, crowd run; d, ducks take off; f, factory; i, in to tree; l, life; o, old town cross; pa, park joy; pe, pedestrian area; r, red kayak; sn, snow mnt; sp, speed bag; t, touchdown pass; w, west wind easy.

Table 2

Details of the experimental videos.

Table 3

QP of the experimental videos.

Fig. 7

Bit rates of the experimental videos (Mbps).

To compare the proposed technique with the conventional ones, we performed MA, mMA, and PLSB-r to the experimental videos. Two conventional techniques using qTCs were also performed with the goal of comparison,^13,14 which are expressed as Adap and Psy since then, respectively. For the purpose of comparing the techniques with similar payload values, in MA and mMA, four bits of additional data are embedded in the $F_M$ of one block, while in PLSB-r, all non-zero quantized AC coefficients in intra-blocks are used for embedding, in Adap, the payload is adjusted to be similar as the proposed technique. However, Psy cannot achieve a similar payload as the proposed technique, so we maximized the payload in Psy.

4.2.

Losslessness Verification Experiment

To verify the losslessness of the proposed technique, we calculated the mean squared error (MSE) value of the extracted data and $S$. The MSE value is calculated as follows:

The MSE values were all 0, which corroborated that the data hiding processes of the three techniques are lossless.

4.3.

Effectiveness Verification Experiment

For the purpose of verifying the effectiveness of the proposed techniques, we evaluated the cover videos in viewpoints of quality, payload, and file-size overhead. $P$ (payload) stands for the size of embedded data. $O$ (file-size overhead) stands for the increase of the video data size and is defined as: $O=F_2-F_1$, where $F_2$ is the data size after data hiding and $F_1$ is the data size before data hiding.

The quality is evaluated using peak signal-to-noise ratio (PSNR) and structural similarity (SSIM),³⁵ which are both calculated between the enriched videos and the baseline videos. Both PSNR value and SSIM value for a pair of videos are the average of all frames.

The payload and file-size overhead results are represented as payload per second and overhead per second in order to help the users of the proposed system to understand them in a kind of practical manner.

The overhead-to-payload ratios are calculated as $\mathrm{ratio}=O/P$. The overhead-to-payload ratio could be considered as a payload efficiency evaluation index of data hiding in the viewpoint of overhead. The file-size increase rates are calculated as $\mathrm{FR}=O/F$ and the payload rates are calculated as $\mathrm{PR}=P/F$, where $F$ stands for the file-size of the baseline video. Negative file-size increase rate values indicate that the file-size of the cover video decreases after data hiding process.

The average values of the experiment results of all the 15 experimental videos for both DVD and BD are shown in Figs. 8Fig. 9–10, and the comparison of the proposed technique with MA, mMA, Adap, and Psy are shown in Table 4. As an example, the output videos of Adap, Psy, and PLSB-r for “aspen,” “ducks take off,” “factory,” “pedestrian area,” and “west wind easy” after data hiding process are shown in Fig. 11 with the baseline video.

Fig. 8

PSNR results of the experimental videos (dB).

Fig. 9

SSIM results of the experimental videos.

Fig. 10

File-size increase rate results of the experimental videos (%).

Table 4

Average results of the comparison between conventional and proposed techniques.

Fig. 11

Baseline video and data hiding results for “aspen,” “ducks take off,” “factory,” “pedestrian area,” and “west wind easy”: (a) baseline, (b) Adap, (c) Psy, and (d) PLSB-r, from top to bottom.

4.4.

Discussion

From Figs. 8Fig. 9Fig. 10–11, we can conclude that the quality of the output videos with data hidden in them are acceptable. From Fig. 10, we can conclude that the data sizes of all the videos decrease after data hiding.

On the other hand, as shown in Fig. 12, note that Psy has much smaller payload which suggests that it is not suitable for comparison. Compared with the rest three techniques with similar payload (in the case of DVD videos, 68.6 Kbps for MA and mMA, 69.4 Kbps for Adap, and 66.6 Kbps for PLSB-r), the proposed technique realizes data size decrease in exchange for a certain degree of the video quality degradation. However, the PSNR values are around 35 dB while the SSIM values are around 0.99, due to which we can consider that the video quality is sufficient. Furthermore, Fig. 11 indicates that the video quality degradation is visually insensitive.

Fig. 12

PSNR versus file-size increase rate.