Reversible data hiding using side-match predictions on steganographic images

Abstract

Information hiding is an important method to achieve multi-media security. Recently, many researchers have paid attention to the reversible data hiding scheme, which can completely recover original multi-media files after the embedded data are extracted. In this paper, a side-match approach is proposed to achieve more capacity in histogram-based reversible data hiding for grayscale images. The histogram is created by exploiting the difference in all the values between pixels and their predictedive values. Experimental results show that our method is capable of providing a great embedding capacity without causing noticeable distortion. In one-level hiding, where it has the best capacity, our method conserves image qualities larger than 48 dB. Furthermore, in multilevel hiding, a rotation strategy is proposed to further improve image qualities. Experimental results show that our method performs better than other existing methods in multilevel hiding cases.

1 Introduction

With the rapid development of network technologies and the coming of the digital era, the Internet has become indispensable for many people. Through the development of the Internet, many new businesses have been developed, such as e-commerce, e-learning, online games, video-on-demand, etc. Furthermore, many existing enterprises have expanded their traditional business activities to the Internet. Every day, thousands of multimedia data are transferred conveniently and efficiently over the Internet. Because digital multimedia data, such as audio, videos, images, texts, etc., have the attributes of easy copying, modification and distribution, the development of the Internet has increased the problems of multimedia security. A way to protect the authentication and ownership of multimedia data has become an important topic, so many researchers have paid a great deal of attention to this topic. One of the most important approaches to this topic is the technique of information hiding.

Many approaches to information hiding have been proposed with different attributes, such as capacity, imperceptibility, undetectability, robustness and reversibility. These attributes are used for various applications, such as secret communication, copyright protection, tampering detection and other human-centered approaches. Information hiding techniques can be categorized into two types: methods in the spatial domain and methods in the frequency domain. In the spatial domain, the secret messages are embedded by changing image pixels directly. On the other hand, in the frequency domain, the image is first transformed into its frequency domain, and then the secret messages are embedded in the transformed coefficients.

Recently, reversible data hiding has drawn many researchers’ attention. Reversibility allows original media to be completely recovered from stego-media after the embedded message is extracted. Many reversible data hiding approaches have been proposed [1–3, 5, 7–18, 21–24]. According to how the data are embedded, these approaches can be classified into three categories: the spatial domain [1, 3, 5, 7–9, 11–18, 24], the frequency domain [10, 22] and other compression types, such as vector quantization (VQ) [2, 21, 23]. In those developed reversible data hiding methods, two main technologies have been widely applied: difference-expansion-based technology [1, 5, 7, 9, 15, 16, 18] and histogram-based technology [8, 11–14, 17, 24]. In 2006, Ni et al. presented a reversible data hiding method based on the histogram [14]. Their method guarantees that the change of each pixel in the stego-image remains within ±1. Therefore, the PSNR value of the stego-image is at least 48 dB. However, their method used the pixel values in the original image to create the histogram, So the peak values of the histogram were not high enough. Some methods used predictive concepts to increase the peak height [3, 4, 11–13, 17, 24]. In 2008, Lin et al. proposed a lossless data hiding scheme based on three-pixel block differences [12]. Their lossless method embeds a message into a cover image using the two differences—between the first and second pixels, as well as between the second and third pixels—in a three-pixel block. In the best case, a three-pixel block can embed two bits “11” and only the central pixel needs to be increased or decreased by 1. In 2008, Lin et al. proposed a multilevel reversible data hiding scheme based on the histogram of difference images [24]. They applied their lossless data hiding method to a cover image many times to enlarge the capacity. In 2008, Hong et al. [4] proposed a reversible data hiding scheme based on histogram-shifting of prediction errors (HSPE). Their method provided advantages of using the median edge detector to design a scheme based on histogram shifting. In 2009, Li et al. proposed a reversible data hiding scheme based on the similarity between neighboring pixels [11]. The difference between two adjacent pixels has a high probability of being a small value. They employed the histogram of the pixel difference sequence to increase the embedding capacity. In 2010, Fallahpour et al. [3] proposed an reversible data hiding approach using the image prediction errors, where the most well-known prediction algorithms, such as the median edge detector (MED) [19], gradient adjacent prediction (GAP) [20], and Jiang et al.’s prediction [6], are tested for the adaptive shifted prediction error (ASPE). From the above developed histogram-based data hiding approaches, we know that Ni et al. provided the first histogram-based approach but not applied the predictive methods to enhance the height of the histogram. Other papers applied the predictive methods to enhance the height. However, sometimes the predictive methods are too simple to create an efficient height. Moreover, no paper providing any strategy to different levels when multi-level data hiding approaches are applied.

In this paper, we propose a new reversible information hiding method based on the histogram for grayscale images. We use the side-match prediction to advance the capacity embedding in histogram-based reversible data hiding methods. All predictive error values are transformed into histograms to create higher peak values. When multilevel hiding is performed, a rotation strategy is proposed to make image quality evaluations higher in empirical experiments. The remainder of this paper is organized in the following way: in Section 2, we introduce some related works of reversible information hiding technology, our proposed scheme is described in Section 3, and some experimental results are shown in Section 4. Finally, we offer some conclusions in Section 5.

2 Related works

In this section, we review Ni et al.’s and Li et al.’s histogram-based reversible data hiding methods [11, 14].

2.1 Ni et al.’s method

Ni et al. proposed a reversible data hiding method in 2006 [14]. Their method uses the histogram of an original image to embed secret messages. In the histogram, they find multiple pairs of peak and zero points, where a peak point corresponds to the pixel value which a maximal number of pixels in the cover image assumes, and a zero point corresponds to the pixel value which no pixel in the cover image assumes. To use a pair of peak and zero points to embed the secret messages, their algorithm is as follows:

• 1. Generate the histogram H(x) with x∈[0, 255] of the original image.

• 2. In the histogram H(x), find a peak point p and a zero point z, where p,z∈[0, 255].

• 3. Shift the values between the peak point and the zero point as follows:

  • (a) If p > z, move the whole part of the histogram H(x) with x∈[z + 1, p – 1] to the left by 1 unit.

  • (b) If p < z, move the whole part of the histogram H(x) with x∈[p + 1, z – 1] to the right by 1 unit.

• 4. Scan the image and embed one secret bit when a pixel with value p is met:

  • (a) If the to-be-embedded bit is 0, the pixel value remains p.

  • (b) If the to-be-embedded bit is 1, the pixel value is set to p + 1 and p – 1 when p is smaller than z and p is greater than z, respectively.

• 5. Output the stego-image, peak point p, and zero point z.

Figure 1 shows an example of Ni et al.’s method. The table in the left is an image with 5 × 5 pixels. The diagram in the right is the histogram, where a peak point p = 163 and a zero point z = 166 are found. Then, pixel values belonging to [164, 165] are moved to the right by 1 unit. The results are shown in Fig. 2.

Fig. 1

Ni et al.’s example

Fig. 2

Results after shifting

Suppose the to-be-embedded data are 11001101. Pixels shown in Fig. 2 are scanned from left to right and from top to bottom. All pixels with a value equal to p = 163 can be used to embed one secret bit. The embedded results are shown in Fig. 3.

Fig. 3

The embedded results

2.2 Li et al.’s method

In 2009, Li et al. provided a histogram-based reversible data hiding method using the adjacent pixel difference (APD) approach, which transforms the cover image into an intermediary difference sequence to increase the frequency of the peak points [11]. A natural image usually contains several smooth areas. The difference between two adjacent pixels has a high probability of being a small value, often close to zero. Various calculations can be applied to an image to generate various difference sequences such that the peak points of these sequences have higher frequencies than the peak points of the histogram of the untransformed image. The APD employs the histogram of the pixel difference sequence to increase the embedding capacity.

Let P be the original gray image with n pixels and P _i be the pixel value with index value i in the scanned sequence. The embedding algorithm is as follows:

• Input: Original image, secret message.

• Output: Stego-image, two pairs of peak and zero points.

• 1. Generate the difference image P ^′ from the original image P. The formula is as follows:

  $$ P_i^{\prime } = \left\{ \begin{gathered} {{P}_i}\quad \,\,\,\quad \quad, if\,i = 0 \hfill \\ {{P}_{{i - 1}}} - {{P}_i}\quad, if\,1 \leqslant i < n \hfill \\ \end{gathered} \right.. $$

• 2. Generate the histogram of the difference image and find the pairs of peak and zero points (PP ₁, CZP ₁) and (PP ₂, CZP ₂) that satisfy CZP ₁ < PP ₁ < PP ₂ < CZP ₂. If no zero point exists, a minimum frequency point is selected, and the extra information of these coefficient values is stored. Then, the minimum frequency point is cleared to become the zero point.

• 3. Shift the histogram as follows:

  • (a) ${{P}_i}^{{\prime \prime }}$ is set to ${{P}_i}^{\prime } - {1}$ if ${{P}_i}^{\prime } \in \left[ {CZ{{P}_{{1}}} + {1},P{{P}_{{1}}} - {1}} \right]$.

  • (b) ${{P}_i}^{{\prime \prime }}$ is set to ${{P}_i}^{\prime } + {1}$ if ${{P}_i}^{\prime } \in \left[ {P{{P}_{{2}}} + {1},CZ{{P}_{{2}}} - {1}} \right]$.

• 4. Embed a secret bit when $P_i^{\prime }$ is equal to PP ₁ or PP ₂ as follows:

  • (a) If the to-be-embedded bit is 0, ${{P}_i}^{{\prime \prime }}$ is set to $P_i^{\prime }$.

  • (b) If the to-be-embedded bit is 1, ${{P}_i}^{{\prime \prime }}$ is set to ${{P}_i}^{\prime } - {1}$ and ${{P}_i}^{\prime } + {1}$ when $P_i^{\prime }$ is equal to PP ₁ and PP ₂, respectively.

• 5. Convert each embedded predictive error value ${{P}_i}^{{\prime \prime }}$ into its embedded pixel value ${{P}_i}^{{\prime \prime \prime }}$ as follows:

  $$ P_i^{{\prime \prime \prime }} = \left\{ \begin{gathered} P_i^{{\prime \prime }}\quad \quad \quad, if\;i = 0 \hfill \\ {{P}_{{i - 1}}} - P_i^{{\prime \prime }}\quad, otherwise \hfill \\ \end{gathered} \right.. $$

• 6. Generate the stego-image from P′′′.

As shown in Fig. 4, a 6 × 4 grayscale image is provided to explain the embedding algorithm. Assume the secret data are “100010010”. In Step 1, the original image is scanned in inverse s-order. Then, a one-dimensional difference sequence P' is generated. In Step 2, two pairs of peak points and zero points, (0, –4) and (2, 5), are selected. In Step 3, values of P' are shifted. In Step 4, secret data are embedded, and the P'' sequence is generated. The secret data are embedded in the grays boxes of the sequence. In Step 5, the other values of the sequence are obtained through the first value $P_0^{{\prime \prime \prime }} = {\text{P}}_0^{{\prime \prime }} = {11}0$. For example, $P_1^{{\prime \prime \prime }} = {{P}_0} - P_1^{{\prime \prime }} = {11}0 - \left( { - {1}} \right) = {111}$. Then, the stego-image is constructed from the P''' sequence. Each pixel difference between the original image and stego-image is at most one.

Fig. 4

An example of the data embedding process of the APD method

3 Our proposed method

In this section, we propose a new histogram-based reversible data hiding scheme. We use the side-match prediction approach to achieve histogram-based reversible data hiding. This method can increase the embedding capacity and conserves the quality of the image. Figure 5 shows the main concept of the side-match prediction, where i > 0 and j > 0. Our predictive method is to employ the neighboring pixels H _{i, j-1} , H _{i-1, j-1} , H _{i-1, j} , and H _{i-1, j+1} to predict the pixel H _{i, j} . Figure 6 shows the flowchart of our method. In the embedding process, predictive error values created by the side-match prediction are used to generate a histogram to embed secret data. In the extracting and reversing process, the side-match prediction is applied to the stego-image, and the created histogram is processed for extracting and reversing. The detail of the embedding algorithm and the extracting and reversible algorithm are shown in the following subsections.

Fig. 5

The main concept of the side-match prediction

Fig. 6

The flowchart of our proposed scheme

3.1 Embedding algorithm

Suppose that the original image is an n × m gray image. H _{i, j} and $H_{{i,j}}^{\prime }$ are the pixel values at location (i, j) before and after being processed, respectively. D _{i, j} is the predictive error value at location (i, j), and $D_{{i.j}}^{\prime }$ is the embedded predictive error value at location (i, j). The embedding algorithm is as follows:

• Input: Original image, secret message.

• Output: Stego-image, two pairs of peak and zero points.

• 1. Input the original image H = {H _0,0, H _0,1, …, H _0,n-1, …, H _1,0, …, H _n-1,n-1}.

• 2. From left to right and from top to bottom, predict each pixel H _{i, j} in the original image to create its predictive error value D _{i, j} as follows:

  • (a) If i = j = 0, then

    $$ {{D}_i}_{{,j}} = {{H}_i}_{{,j}} - {128}{.} $$

    (1)

  • (b) If i = 0 and j ≠ 0, then

    $$ {{D}_i}_{{,j}} = {{H}_i}_{{,j}} - {{H}_i}_{{,j - {1}}}. $$

    (2)

  • (c) If i ≠ 0 and j = 0, then

    $$ {{D}_{{i,j}}} = {{H}_{{i,j}}} - \left\lfloor {\frac{{{{H}_{{i - 1,j}}} + {{H}_{{i - 1,j + 1}}}}}{2}} \right\rfloor . $$

    (3)

  • (d) If i ≠ 0 and j = m –1, then

    $$ {{D}_{{i,j}}} = {{H}_{{i,j}}} - \left\lfloor {\frac{{{{H}_{{i,j - 1}}} + {{H}_{{i - 1,j - 1}}} + {{H}_{{i - 1,j}}}}}{3}} \right\rfloor . $$

    (4)

  • (e) Else,

    $$ {{D}_{{i,j}}} = {{H}_{{i,j}}} - \left\lfloor {\frac{{{{H}_{{i,j - 1}}} + {{H}_{{i - 1,j - 1}}} + {{H}_{{i - 1,j}}} + {{H}_{{i - 1,j + 1}}}}}{4}} \right\rfloor . $$

    (5)

• 3. Create the histogram H(x) with x ∈ [–255, 255] from all predictive error values.

• 4. Find two pairs of peak and zero point (P ₁, Z ₁) and (P ₂, Z ₂) satisfying Z ₂ < P ₂ < P ₁ < Z ₁.

• 5. Shift the histogram as follows:

  • (a) $D_{{i,j}}^{\prime }$ is set to D _{i, j}  + 1 if D _{i, j} ∈ [P ₁ + 1, Z ₁ – 1].

  • (b) $D_{{i,j}}^{\prime }$ is set to D _{i, j} – 1 if D _{i, j} ∈ [Z ₂ + 1, P ₂ – 1].

• 6. Embed the secret message as follows:

  • (a) If the to-be-embedded bit is 0, $D_{{i,j}}^{\prime }$ is set to D _{i, j} .

  • (b) If the to-be-embedded bit is 1, $D_{{i,j}}^{\prime }$ is set to D _{i, j}  + 1 and D _{i, j} – 1 when D _{i, j} is equal to P ₁ and P ₂, respectively.

• 7. From left to right and from top to bottom, convert each embedded predictive error value $D_{{i,j}}^{\prime }$ into its embedded pixel value $H_{{i,j}}^{\prime }$.

  • (a) If i = j = 0, then

    $$ H_{{i,j}}^{\prime } = D_{{i,j}}^{\prime } + {128}{.} $$

    (6)

  • (b) If i = 0 and j ≠ 0, then

    $$ H_{{i,j}}^{\prime } = D_{{i,j}}^{\prime } + {{H}_i}_{{,j - {1}}}. $$

    (7)

  • (c) If i ≠ 0 and j = 0, then

    $$ H_{{i,j}}^{'} = D_{{i,j}}^{'} + \left\lfloor {\frac{{{{H}_{{i - 1,j}}} + {{H}_{{i - 1,j + 1}}}}}{2}} \right\rfloor . $$

    (8)

  • (d) If i ≠ 0 and j =  m –1, then

    $$ H_{{i,j}}^{'} = D_{{i,j}}^{'} + \left\lfloor {\frac{{{{H}_{{i,j - 1}}} + {{H}_{{i - 1,j - 1}}} + {{H}_{{i - 1,j}}}}}{3}} \right\rfloor . $$

    (9)

  • (e) Else,

    $$ H_{{i,j}}^{'} = D_{{i,j}}^{'} + \left\lfloor {\frac{{{{H}_{{i,j - 1}}} + {{H}_{{i - 1,j - 1}}} + {{H}_{{i - 1,j}}} + {{H}_{{i - 1,j + 1}}}}}{4}} \right\rfloor . $$

    (10)

• 8. Output stego-image, (P ₁, Z ₁), and (P ₂, Z ₂).

As shown in Fig. 7, a 5 × 5 grayscale original image H = {H _0,0, H _0,1, …, H _0,4, H _1,4, …, H _4,4} is given to explain our embedding algorithm. We predict the pixels first. For example,

$$ \matrix{{*{20}{c}} {{{D}_{{0,0}}} = {{H}_{{0,0}}} - {128} = {126} - {128} = - {2},} \hfill \\ {{{D}_{{0,{1}}}} = {{H}_{{0,{1}}}} - {{H}_{{0,0}}} = {125} - {126} = - {1},} \hfill \\ } $$

$$ {{D}_{{1,0}}} = {{H}_{{1,0}}} - \left\lfloor {\frac{{{{H}_{{0,0}}} + {{H}_{{0,1}}}}}{2}} \right\rfloor = 125 - \left\lfloor {\frac{{126 + 125}}{2}} \right\rfloor = 0, $$

$$ \begin{gathered} {{D}_{{1,1}}} = {{H}_{{1,1}}} - \left\lfloor {\frac{{{{H}_{{1,0}}} + {{H}_{{0,0}}} + {{H}_{{0,1}}} + {{H}_{{0,2}}}}}{4}} \right\rfloor \; \hfill \\ \quad = 126 - \left\lfloor {\frac{{125 + 126 + 125 + 124}}{4}} \right\rfloor = 1 \hfill \\ \end{gathered} $$

and so on. The results are shown in Fig. 8. The histogram created from all predictive error values is also shown in Fig. 8. According to the histogram, we have found two pairs of peak and zero points: (P ₁, Z ₁) = (0, 3) and (P ₂, Z ₂) = (–1, –3). The results and the histogram after shifting are shown in Fig. 9.

Fig. 7

The original image

Fig. 8

The predictive error values and their histogram

Fig. 9

The predictive error values and their histogram after shifting

Then, we embed the secret messages. The predictive error values equivalent to P ₁ or P ₂ are used to embed the secret messages. Assume secret message I = 101001101000110₍₂₎. After secret message I is embedded, the predictive error values and their histogram are shown in Fig. 10. Finally, the predictive error values are converted into pixel values. For example,

$$ \matrix{{*{20}{c}} {H_{{0,0}}^{\prime } = D_{{0,0}}^{\prime } + {128} = - {3} + {128} = {125},} \hfill \\ {H_{{0,{1}}}^{\prime } = D_{{0,{1}}}^{\prime } + {{H}_{{0,0}}} = - {2} + {126} = {124},} \hfill \\ } $$

$$ H_{{1,0}}^{'} = D_{{1,0}}^{'} + \left\lfloor {\frac{{{{H}_{{0,0}}} + {{H}_{{0,1}}}}}{2}} \right\rfloor = 0 + \left\lfloor {\frac{{126 + 125}}{2}} \right\rfloor = 125, $$

$$ \begin{gathered} {{H}^{'}}_{{1,1}} = {{D}^{'}}_{{1,1}} + \left\lfloor {\frac{{{{H}_{{1,0}}} + {{H}_{{0,0}}} + {{H}_{{0,1}}} + {{H}_{{0,2}}}}}{4}} \right\rfloor \hfill \\ \quad \quad = 2 + \left\lfloor {\frac{{125 + 126 + 125 + 124}}{4}} \right\rfloor = 127, \hfill \\ \end{gathered} $$

Fig. 10

The predictive error values and their histogram after embedding

3.2 Extracting and reversing the algorithm

In the extracting and reversing process, the secret message is extracted, and the embedded pixel values are reversed. The extracting and reversing algorithm is shown as follows:

• Input: Stego-image H′, two pairs of peak and zero points (P ₁, Z ₁) and (P ₂, Z ₂).

• Output: Original image, secret message.

• 1. Process each pixel of stego-image H′ from left to right first and then from top to bottom by following Step 2 to Step 4 repeatedly.

• 2. Create predictive error value $D_{{i,j}}^{\prime }$ from H′.

• 3. Use (P ₁, Z ₁) and (P ₂, Z ₂) to extract the secret message and recover the predictive error values as follows:

  • (a) If the $D_{{i,j}}^{\prime }$ is equal to P ₁ or P ₂, the secret bit 0 is extracted, and the predictive error is recovered as ${{D}_i}_{{,j}} = D_{{i.j}}^{\prime }$.

  • (b) If the $D_{{i,j}}^{\prime }$ is equal to P ₁ +1 or P ₂ – 1, the secret bit 1 is extracted and the predictive errors are recovered as ${{D}_i}_{{,j}} = D_{{i.j}}^{\prime } - 1$ or ${{D}_i}_{{,j}} = D_{{i.j}}^{\prime } + 1$, respectively.

  • (c) If $D_{{i,j}}^{\prime }\left[ {{{P}_{{1}}} + {2},{{Z}_{{1}}}} \right]$, recover the predictive error as ${{D}_i}_{{,j}} = D_{{i,j}}^{\prime } - {1}$.

  • (d) If $D_{{i,j}}^{\prime }\epsilon \left[ {{{Z}_{{2}}},{{P}_{{2}}} - {2}} \right]$, recover the predictive error as ${{D}_i}_{{,j}} = D_{{i,j}}^{\prime } + {1}$.

• 4. Convert predictive error values D _{i, j} into original pixel value H _{i, j} .

• 5. Output the original image and the secret message.

Now, we perform extracting and reversing operations on the embedded results shown in Fig. 11. The two inputted pairs of peak and zero points are (P ₁, Z ₁) = (0, 3) and (P ₂, Z ₂) = (–1, –3). We process the first pixel value $H_{{0,0}}^{\prime }$ first. $D_{{0,0}}^{\prime } = H_{{0,0}}^{\prime } - {128} = {125} - {128} = - {3}$. We find that $D_{{0,0}}^{\prime } = - {3}$ is in [Z ₂, P ₂ – 2], so ${{D}_{{0,0}}} = D_{{0,0}}^{\prime } + {1} = - {2}$. Then, we calculate the original pixel value ${{H}_{{0,0}}} = {{D}_{{0,0}}} + {128} = - {2} + {128} = {126}$. Next, the second pixel value $H_{{0,1}}^{\prime }$ is processed. $D_{{0,1}}^{\prime } = H_{{0,1}}^{\prime } - {{H}_{{0,0}}} = {124} - {126} = - {2}$. We find that $D_{{0,1}}^{\prime } = - {2}$ is equal to P ₂ – 1, so secret bit 1 is extracted, and the predictive error value is recovered as ${{D}_{{0,{1}}}} = D_{{0,1}}^{\prime } + {1} = - {2} + {1} = - {1}$. Finally, we calculate the original pixel value ${{H}_{{0,}}}_{{1}} = {{D}_{{0,}}}_{{1}} + {126} = - {1} + {126} = {125}$. Similarly, other pixel values $H_{{i,j}}^{\prime }$ are processed in order to generate their original pixel values H _i , _j.

Fig. 11

The stego-image

3.3 Processing directions of side-match approaches

Side-match approaches can be performed from various directions. As shown in Fig. 12, predicting pixel H _{i, j} by side-match approaches can come from different directions and has various choices. For example, from the upper-left corner, {H _{i, j–1}, H _{i–1, j–1}, H _{i–1, j} , H _{i–1, j+1}}, {H _{i, j–1}, H _{i–1, j–1}, H _{i–1, j} }, {H _{i, j–1}, H _{i-1, j} } and {H _{i, j–1}} are some possible choices to predict pixel H _i,j . Similarly, from the upper-right corner, {H _{i, j+1}, H _{i-1, j+1}, H _{i-1, j} , H _{i-1, j-1}}, {H _{i, j+1}, H _{i-1, j+1}, H _{i-1, j} }, {H _{i, j+1}, H _{i-1, j} } and {H _{i, j+1}} are some possible choices to predict pixel H _{i, j} . The algorithm shown in Section 3.1 is the case {H _{i, j–1}, H _{i–1, j–1}, H _{i–1, j} , H _{i–1, j+1}} which is from the upper-left corner. Other cases can be implemented similarly. The experimental results of this paper are created by using {H _{i, j+1}, H _{i-1, j} } to predict H _{i, j} from the upper-right corner.

Fig. 12

A pixel H _i , _j and its 8 adjacent pixels

3.4 Image-rotation strategies for multilevel data hiding

Our histogram-based reversible data hiding scheme guarantees that the change of each pixel in the stego-image remains within ±1. Therefore, the stego-image has good image quality. The image quality of the stego-image is usually evaluated by the peak signal to noise ratio (PSNR) which is defined as:

$$ {\text{PSNR}} = 10 \times {{\log }_{{10}}}\frac{{{{{255}}^2}}}{\text{MSE}}\left( {\text{dB}} \right), $$

(11)

where MSE is the mean square error between the original image and the stego-image. For the 512 × 512 gray image, the MSE is defined as:

$$ {\text{MSE}} = \frac{1}{{512 \times 512}}\sum\limits_{{i = 0}}^{{511}} {\sum\limits_{{j = 0}}^{{511}} {{{{\left( {{{H}_{{i,j}}} - H_{{i,j}}^{\prime }} \right)}}^2}} }, $$

(12)

where H _{i, j} and $H_{{i,j}}^{\prime }$ are the pixel values of the original image and the stego-image, respectively. If the difference value of each pixel between the original image and the stego-image remains ±1, the PSNR value is larger than $10 \times {{\log }_{{10}}}\frac{{255 \times 255}}{1} = 10 \times 4.8130 = 48.13\;{\text{dB}}$. To increase the embedding capacity, the embedding procedure can be applied to the cover images many times. The final embedded results are still reversible. This is called the multilevel data hiding approach [12, 24]. The multilevel data hiding approach can increase the embedding capacity, but the image quality of the embedded results will decline.

We use our reversible data hiding method to perform the multilevel data hiding scheme. Moreover, an image-rotation strategy is proposed to further advance image quality. As shown in Fig. 13, we perform a clockwise 180° rotation on the test image after the embedding procedure is finished at each level. A simple example is given in Fig. 14 to explain our idea. We know that a natural image usually contains image-gradient parts, that is, the gray values of neighboring pixels are increasing or decreasing. Figure 14 shows a 9-pixel artificial example where the gray values of the 9 pixels increase from left to right. With the predicted left-to-right direction, the first-level embedded results are shown in Fig. 14(a). Most pixels increase by 1 for the reason that the shifting operation will increase the predictive error values by 1 based on the assumption that 0 is a peak point. Based on that same assumption, Fig. 14(b) shows the second-level embedded results also using the predicted left-to-right direction. Again, most pixels increase by 1. Compared to the original pixels, most pixels have increased by 2. However, as shown in Fig. 14(c), if a predicted right-to-left direction is used in the second-level data hiding, most pixels will decrease by 1. Therefore, compared with the original pixels, most pixels remain unchanged after the second-level data hiding. From the above observations, we believe that our image-rotation strategy has significantly lifted the quality of multilevel data hiding.

Fig. 13

The clockwise 180° rotation of Lena

Fig. 14

An example to explain the rotation operation: a Embedded from the left-to-right direction in the first step. b Embedded from the left-to-right direction in the second step. c Embedded from the right-to-left direction in the second step

3.5 Overflow and underflow solutions

After secret messages are embedded in an image, the change of each pixel remains within ±1. Therefore, if pixel values are equal to 0 or 255 in the original image, they may become –1 and 256 in the stego-image and cause underflow and overflow problems. In order to avoid this problem, we use a pre-processing method [5]. When the pixel values are equal to 0 or 255 in the original image, they are changed into 1 or 254 in advance, respectively. For each pixel value 1, a flag bit is needed to record that its original pixel value is 0 or 1. Similarly, one flag bit is needed for each pixel value 254. Therefore, for each pixel with values 1 or 254, if the pixel is changed from 0 or 255, the flag bit is set to 1; otherwise, the flag bit is set to 0.

4 Experimental results

In this section, we display the performance of our scheme. In our experiments, we used random numbers as secret messages and 512 × 512 grayscale images as the cover images. Figure 15 shows the seven 512 × 512 grayscale test images Airplane, Baboon, Boats, Goldhill, Lena, Peppers and Tiffany. Table 1 shows a comparison among Ni et al.’s method [14], Tsai et al.’s method [17], Li et al.’s method [11], and our scheme when the embedding algorithm is applied once, where the capacity represents the embedded bit number and the bbp indicates bits per pixel. Our method has the largest capacity. The average capacity of our scheme is about 7 times of Ni et al.’s method, but the image qualities of their and our approaches are similar. Furthermore, our average capacity is 13% higher than that of Li et al.’s method. Table 2 shows a comparison between Fallahpour et al.’s method [3] and our scheme. In Fallahpour et al.’s method, they used the main peak in the adaptive shifted prediction error (ASPE) with three prediction types: the GAP method [20], Jiang et al.’s method [6], and the MED method [19]. Our average capacity is 12.50% higher, 20.10% higher, 19.51% higher than that of the GAP method, Jiang et al.’s method, and the MED method. Tables 3 and 4 show the embedding results of different levels without and with the 180° rotations, respectively. The results show that the rotation operation can advance the image qualities so that more secret data can be embedded based on the same image quality. Figure 16 shows the relationship between capacities and PSNR values for multilevel data embedding when levels are between 1 and 12. It demonstrates that smooth images, such as Airplane, have larger embedding capacities and better PSNR values than that of complex images, such as Baboon. Table 5 shows the bit numbers of overhead for pre-processing the overflow and underflow problems at different levels. Most images have low overhead. Table 6 shows a comparison among Lin and Hsueh’s method [12], Zeng et al.’s method [24], Li et al.’s method [11], Hsiao et al.’s method [5] and our scheme with PSNR values close to 30 dB, where Hsiao et al.’s method is difference-expansion-based. Our method includes the rotation operation, and the capacity has excluded the overhead of processing overflow and underflow problems. The number of levels of our scheme is shown in the parentheses. As shown in Table 6, our average capacity is 7% higher, 18% higher, 21% higher and 17% higher than that of Lin and Hsueh’s method [12], Zeng et al.’s method [24], Li et al.’s method [11] and Hsiao et al.’s method [5], respectively. Figure 17 demonstrates the compared results of the proposed scheme with other reversible schemes for the seven images. Table 7 shows a comparison among Kim et al.’s [8], Luo et al.’s [13] and our scheme when PSNR values are close to 48 db, 44 db, or 40 db. The parameter embedding level (EL for short) is the shifting distance used in Kim et al.’s and Luo et al.’s methods. As shown in Table 7, our capacities are the largest in all cases.

Fig. 15

Seven tested images

Table 1 The comparison among Ni et al.’s, Tsai et al.’s, Li et al.’s, and our proposed methods

Table 2 The comparison between Fallahpour et al.’s [3] and our proposed methods

Table 3 The experimental results of different layers without using the clockwise 180° rotation

Table 4 The experimental results of different layers using the clockwise 180° rotation

Fig. 16

Relationships between capacities and PSNR values in our scheme with the clockwise 180° rotation for one to twelve levels

Table 5 The bit numbers of overhead for pre-processing the overflow and underflow problems

Table 6 The comparison for multilevel data hiding when the image quality is close to 30 dB

Fig. 17

Comparison of the results of the proposed scheme with other reversible schemes of the seven images

Table 7 Comparisons of our, Kim et al.’s [8] and Luo et al.’s [13] results with the 3*3 block partition

5 Conclusions

In this paper, we propose a side-match prediction method to strengthen the lossless data hiding technique based on the histogram. In our proposed side-match prediction methods, pixels can be predicted more precisely to create higher peak points than that of Li et al.’s method [11]. The predictive error values to create the histogram are as many as the pixels in the original image. Furthermore, an image-rotation scheme is proposed to come up with better results for multi-level data hiding. Experimental results show that our proposed schemes have better embedded results than that of existing approaches for single-level and multi-level data hiding.