1 Introduction

The reversible data embedding method can embed messages into multimedia, e.g., images [1, 3, 4, 6, 7, 9,10,11,12,13, 15,16,17, 21,22,23], videos [5], DNA sequences [2, 8], and compression codes [18,19,20]. After the data have been embedded, the multimedia is very similar to the original multimedia, thus the method is very suitable for some applications, e.g., steganography, watermarking, and annotation [14].

There are four types of reversible data embedding methods, i.e., difference expansion [23], prediction error expansion [6, 10, 13, 21, 22], histogram shifting [17], and dual stego-images [8–16. In 2003, Tian [1] expanded the difference between two adjacent pixels to embed one bit. Fig. 1 shows a diagram of the difference expansion method, where {P 1,  P 2} denote two cover pixels, and \( \left\{{P}_1^{\prime },\kern0.5em {P}_2^{\prime}\right\} \) denote two stego pixels. Obviously, difference expansion may cause serious visual distortion of the stego-image. In order to avoid this distortion, Thodi and Rodriguez [21] utilized an inherent edge-detection method to derive the prediction value of the cover pixel. Afterwards, the prediction error between the cover pixel and its prediction value was expanded to embed one bit. Fig. 2 shows the color of most prediction errors as black, indicating that most prediction errors are small. As a result, the expansion of the prediction error does not cause serious distortion of the image.

Fig. 1
figure 1

Difference expansion method

Full size image
Fig. 2
figure 2

Prediction error expansion method

Full size image

In 2006, Ni et al. [17] proposed a histogram shifting method that only modifies the cover pixel between the peak point and the zero point to embed messages and maintain satisfactory image quality. Fig. 3 shows a histogram of cover pixels, where the peak point means the cover pixel with most occurrence frequency, and the zero point means the cover pixel with lowest occurrence frequency. The cover pixels between the peak point and the zero point were shifted by one unit to create an embedding space. Afterwards, the cover pixels that were equal to the peak point are used to embed messages. The histogram shifting method effectively can control the distortion of each pixel within 1. However, this method cannot embed a large amount of data.

Fig. 3
figure 3

Histogram shifting method

Full size image

Different from the three kinds of methods mentioned above, Chang et al. [1] skillfully utilized the exploiting modification direction (EMD) [25] to embed base-5 digits into two identical images. The method needs more spaces to storage two stego-images. However, any third party cannot efficiently extract data from one of the stego-images, indicating that the kind of method provides greater security. The method modifies all pixels, where the modification level ranges from 0 to 2. Lee et al. [11, 12] expanded the number of directions to reduce the number of modified pixels and to control the modification level between 0 and 1, thus the method can maintain the satisfactory quality of the stego-image. In addition, Chang et al. [4] utilized the magic matrix to embed more bits into the cover-image. However, in the data embedding phase, they modified the pixels extensively, causing the image quality to decrease. Different from the above methods, Horng et al. [7] designed an embedding mechanism to embed K secret images and (N – K) cheating images into N stego-images. However, each pixel in the stego image only used to embed one secret bit.

In 2016, Jana et al. [9] used the pixel value differencing (PVD) [24] and difference expansion [23] to embed secret data into two stego-images. First of all, they calculated the deviation between the pre-determined lower bound and the difference of two adjacent pixels to generate the reference information of the image recovery. Afterwards, two adjacent pixels were duplicated to embed secret data and the reference information of the image recovery, where the PVD method [24] was used to embed four secret bits into the first pixel-pair and the difference expansion was used to embed the reference information of the image recovery and one secret bit.

Unlike in the direction-based hiding methods, Lu et al. [15] designed several embedding rules according to least significant bit (LSB) matching, where each pixel was used to embed only one bit. In order to embed more bits and maintain satisfactory quality of the stego-image, Lu et al. [16] proposed a center folding strategy (CFS) that adaptively encodes several bits as the smaller digits. However, CFS cannot decrease the frequency of occurrence of the largest value. In this paper, we propose a dynamic encoding strategy to reduce the frequency of occurrence of the largest value. Thus, we can effectively encode massive digits as the smaller values.

The rest of the paper is organized as follows. Sections 2 and 3 present the CFS hiding method and the proposed method, respectively. Section 4 compares the proposed method and the five related methods in terms of the embedding rate and the quality of the stego-image. The conclusions are presented in Section 5.

2 Related work

Lee et al. proposed a direction-based hiding strategy that can embed base-5 digits into two stego-images, as shown in Fig. 4. Assume that a pair of pixels {P 1 , 1 ,  P 1 , 2} is {5, 14} and two secret digits are {4, 2}. First of all, the pixel-pair is duplicated to embed two secret digits. According to the fourth blue arrow-shaped path in Fig. 4, the first pixel-pair is modified to embed the first secret digit “4”, i.e., \( {P}_{1,1}^{\prime }={P}_{1,1}+1=5+1=6 \) and \( {P}_{1,2}^{\prime }={P}_{1,2}-1=14-1=13 \). Afterwards, the second pixel-pair is modified according to the second red arrow-shaped path, i.e., \( {P}_{1,1}^{{\prime\prime} }={P}_{1,1}=5 \) and \( {P}_{1,2}^{{\prime\prime} }={P}_{1,2}+1=14+1=15 \). The method controls the modification level of pixel within 1, thereby maintaining good image quality. However, the method cannot effectively embed greater digits.

Fig. 4
figure 4

Direction-based hiding method

Full size image

Chang et al. [4] used a magic matrix to embed base-9 secret digits into two stego-images, thus the hiding capacity of Chang et al.’s method is higher than Lee et al.’s method. The magic matrix is generated by

$$ M\left({P}_{x, y},\kern0.5em {P}_{x, y}\right)=\left({P}_{x, y}+3\times {P}_{x, y}\right) \mod 9. $$
(1)

M(P x,y , P x,y ) represents the value of the magic matrix, and P x,y represents the cover pixel. Fig. 5 shows the magic matrix. Assume that the cover pixel is 5 and the secret digit is 4. The cover pixel “5” is duplicated and mapped into the magic matrix, i.e., M(5, 5) = (5 + 3 × 5) mod 9 = 2. The matrix value M(5, 5) is not equal to the secret digit “4,” thus the pixels {5, 5} are modified according to the coordinates of diagonal of the current matrix value. The left-top matrix value M(4, 6) is matched with the secret data, therefore its coordinates {4, 6} are used as the stego pixels. Although the method can embed base-9 secret digits, the modification level of pixel is large, decreasing the image quality.

Fig. 5
figure 5

Magic matrix based hiding method

Full size image

In 2015, Lu et al. [16] proposed a CFS hiding method that decreases each decimal digit by the median to reduce the modification level in the data embedding phase. Fig. 6 shows a flowchart of the CFS hiding method.

Fig. 6
figure 6

Center folding strategy

Full size image

First, the set of K embedded bits {s 1,  s 2,  …,  s K } is transformed into a decimal value d i , where \( {d}_i=\sum_{j=1}^K{s}_j\times {2}^{j-1} \). The notation i denotes the ID number of the decimal value. The decimal value d i ranges from 0 to 2k − 1, i.e., 0 ≤ d i  ≤ 2k − 1. Afterwards, the decimal value d i is reduced by \( {d}_i^{\prime }={d}_i-{2}^{K-1} \), making that the range of the reduced value \( {d}_i^{\prime } \) is limited within [−2K − 1,  2K − 1 − 1], i.e., \( -{2}^{K-1}\le {d}_i^{\prime}\le {2}^{K-1}-1 \). Finally, the reduced digit \( {d}_i^{\prime } \) is embedded into two stego-images, i.e., \( {P}_{x, y,1}={P}_{x, y}+\left\lfloor \frac{d_i^{\prime }}{2}\right\rfloor \) and \( {P}_{x, y,2}={P}_{x, y}-\left\lceil \frac{d_i^{\prime }}{2}\right\rceil \).

The above procedures are explained further by the following example. Let K = 3. Assume that the three embedded bits are {1,  1,  1} and that one cover pixel P 1 , 1 is 105. The three bits {1,  1,  1} are transformed into the decimal value d 1, i.e., \( {d}_1=\sum_{j=1}^3{2}^{j-1}\times {s}_j={2}^0\times 1+{2}^1\times 1+{2}^2\times 1=7 \). The decimal value d 1 is decreased by \( {d}_1^{\prime }={d}_1-{2}^{K-1}=7-{2}^{3-1}=3 \). Finally, the reduced value \( {d}_1^{\prime }=3 \) is embedded into two stego pixels, i.e., \( {P}_{1,1,1}={P}_{1,1}+\left\lfloor \frac{d_1^{\prime }}{2}\right\rfloor =105+\left\lfloor \frac{3}{2}\right\rfloor =106 \) and \( {P}_{1,1,2}={P}_{1,1}-\left\lceil \frac{d_1^{\prime }}{2}\right\rceil \) \( =105-\left\lceil \frac{3}{2}\right\rceil =103 \).

When the legal user received two stego-images, he/she can use the following procedure to extract secret data and recover the cover image, as shown in Fig. 7. First of all, the differences between pixels in two stego-images are calculated to derive the encoded digits, i.e., \( {d}_i^{\prime }={P}_{x, y,1}-{P}_{x, y,2} \). After that, the encoded digits are decoded by \( {d}_i={d}_i^{\prime }+{2}^{K-1} \). Finally, each decoded digits can be transformed into K secret bits.

Fig. 7
figure 7

Flowchart of data extraction and image recovery of the CFS hiding method

Full size image

The following example is used to further explain the extraction and recovery procedures. The pixels in two stego-images are 106 and 103, respectively, hence the difference between two pixels is 3 and it is just the encoded digit. Then, the encoded digit can be decoded correctly by \( {d}_1={d}_1^{\prime }+{2}^{3-1}=3+4=7 \). Finally, the decimal digit is converted into three secret bits, i.e., {1, 1, 1}. In addition, the cover pixel was recovered losslessly by \( {P}_{x, y}=\left\lceil \frac{P_{x, y,1}+{P}_{x, y,2}}{2}\right\rceil =\left\lceil \frac{106+103}{2}\right\rceil =105 \).

The CFS method can reduce the embedded digits from [0, 2K – 1] to [−2K − 1, 2K − 1 − 1]. However, it cannot decrease the frequency of occurrence of the largest value. Fig. 8 shows that the CFS method with K = 2 cannot effectively reduce the number of the largest value. This shortcoming decreases the visual quality of the stego-image.

Fig. 8
figure 8

Results of encoding the embedded image by the CFS method with K = 2

Full size image

3 Proposed method

In the Section, we proposed the dynamic encoding strategy to reduce the number of the largest values.

3.1 Dynamic encoding and data embedding

Fig. 9 shows the flowchart of our data embedding. A set of K bits {s 1,  s 2,  …,  s K } is converted into a decimal value d i , i.e., \( {d}_i=\sum_{j=1}^K{s}_j\times {2}^{j-1} \) and 0 ≤ d i  ≤ 2K − 1. The notation i denotes the ID number of the decimal value. In order to encode the decimal value d i , one codebook with the size of 2K is generated, where the initial values of codewords and their indices are set sequentially from 0 to 2K − 1. The index of codewords can be used effectively to replace the decimal values, thereby reducing the modification level. The encoding procedure is as follows

Fig. 9
figure 9

Flowchart of data embedding of the proposed method

Full size image

The first decimal value is matched with the codeword from the codebook, and its index I 1 is used to represent the decimal value. Then, the index is encoded further by the formula

$$ {I}_i^{\prime }=\left\{\begin{array}{l}\frac{I_i}{2},\kern2.5em \mathrm{if}\kern0.5em {I}_i\kern0.5em \mathrm{is}\ \mathrm{an}\ \mathrm{even}\ \mathrm{number},\\ {}-\frac{I_i+1}{2},\kern0.5em \mathrm{otherwise}.\end{array}\right. $$
(2)

Figure 10 compares the original decimal digits and the encoded indices \( {I}_i^{\prime } \). Moreover, the index of the codeword is updated from I to 0. The updating procedure helps match the next decimal value with the first codeword, thereby encoding the smaller digit. Note that the indices of other codewords are increased by 1 to ensure the validity of the codebook. Finally, the encoded index \( {I}_i^{\prime } \) is embedded into two stego-images, i.e.

Fig. 10
figure 10

Comparison of the decimal digits and the encoded indices

Full size image
$$ {P}_{x, y,1}=\left\{\begin{array}{l}{P}_{x, y}+\left\lfloor \frac{I_i^{\prime }}{2}\right\rfloor, \kern0.5em \mathrm{if}\kern0.5em r=0,\\ {}{P}_{x, y}-\left\lceil \frac{I_i^{\prime }}{2}\right\rceil, \kern0.5em \mathrm{if}\kern0.5em r=1,\end{array}\right.\;\mathrm{and}\;{P}_{x, y,2}=\left\{\begin{array}{l}{P}_{x, y}-\left\lceil \frac{I_i^{\prime }}{2}\right\rceil, \kern0.5em \mathrm{if}\kern0.5em r=0,\\ {}{P}_{x, y}+\left\lfloor \frac{I_i^{\prime }}{2}\right\rfloor, \kern0.5em \mathrm{if}\kern0.5em r=1,\end{array}\right. $$
(3)

where r is a random value, which is generated by the pre-determined random seed [7, 9, 11].

The above procedures can be illustrated further by the following algorithm.

  • Step 1: Convert a set of K secret bits into a decimal value, i.e., \( {d}_i=\sum_{j=1}^K{s}_j\times {2}^{j-1} \).

  • Step 2: Generate one codebook, where it consists of 2K codewords.

  • Step 3: Select an index I i from the codebook, where its codeword is equal to the decimal value.

  • Step 4: Reduce the index by Eq. (2).

  • Step 5: Classify the pixel P x , y into the embeddable pixels and non-embeddable pixels. The pixels between 2K – 1 and 256 – 2K – 1 are labeled as the embeddable pixels. Otherwise, other pixels are the non-embeddable pixels.

  • Step 6: According to the pre-determined random value, embed the reduced index \( {I}_i^{\prime } \) into two stego pixels {P x , y , 1,  P x , y , 2} by Eq. (3).

  • Step 7: Update the index of the codeword, i.e., modifying the index of the selected codeword from I i to 0 and increasing the index of the other codewords by 1.

  • Step 8: Perform the above steps for the next set of secret bits until all secret bits have been embedded.

Figure 11 illustrates the above procedures. Assume that the 12 embedded bits are {1,  1,  1,  1,  1,  1,  0,  0,  1,  0,  0,  1} and the four cover pixels are {105, 105, 8, 30}. Let K = 3 and r = {0, 0}. As a result, one codebook with the size of 23 is established, where the initial values of the codewords and their indices are set sequentially from 0 to 7. The first trio of bits {1, 1, 1} are transformed into a decimal digit, i.e., d 1 = 1 × 20 + 1 × 21 + 1 × 22 = 7. The procedure for transforming other bits is the same as the above procedure

Fig. 11
figure 11

Example of dynamic encoding and embedding

Full size image

These decimal digits are reduced by the following procedure. First, the first decimal digit d 1 = 7 matches the last codeword from the codebook, thus the first decimal digit is replaced by the index of the last codeword, i.e., I = 7. Then, the index is reduced by Eq. (2), i.e., I ′ =  − (7 + 1)/2 =  − 4. In addition, the index of the codeword is updated from 7 to 0, thereby enhancing the possibility of priority-based matching.

The second decimal digit d 2 = 7 matches the first codeword in the updated codebook, thus its index “0” is used to represent the second decimal digit. The codebook remains unchanged because the index of the codeword “7” is 0. The procedure for encoding other indices is the same as the above procedure.

After the above procedure, these encoded indices {−4,  0,  2,  0} are embedded into the cover-image to obtain two stego-images. The first encoded index \( {I}_1^{\prime }=-4 \) is embedded into the first cover pixel P 1 , 1 = 105 to obtain two stego-pixels, i.e., \( {P}_{1,1,1}=105+\left\lfloor \frac{-4}{2}\right\rfloor =103 \) and \( {P}_{1,1,2}=105-\left\lceil \frac{-4}{2}\right\rceil =107 \). Then, the second encoded index I 2 = 0 is embedded into the second pixel P 1 , 2 = 105 to obtain two stego-pixels, i.e., \( {P}_{1,1,1}=105+\left\lfloor \frac{0}{2}\right\rfloor =105 \) and \( {P}_{1,1,2}=105-\left\lceil \frac{0}{2}\right\rceil =105 \). Fig. 11 shows the results of dynamic encoding and embedding.

The proposed method can embed a larger amount of secret data and maintain good image quality. However, a few overflow and underflow problems occur in the data embedding phase. In order to avoid these problems, the proposed method classifies the cover pixels into the embeddable pixels and non-embeddable pixels, as shown in Fig 12. The cover pixels between 2K – 1 and 256 – 2K – 1 are classified into the embeddable pixels because the modification level of pixel ranges from –2K – 1 to 2K – 1 – 1. The non-embeddable pixels remain unchanged to effectively avoid the overflow and underflow problems. In addition, the strategy does not need to any extra data to discriminate between the embeddable pixels and non-embeddable pixels.

Fig. 12
figure 12

Solution for the overflow and underflow problems by pixel classification

Full size image

3.2 Dynamic decoding and image recovery

Fig. 13 shows the flowchart of our extraction and recovery procedure. When the legal user received two stego-images, he/she can correctly decode the embedded bits and losslessly recover the original image. First of all, a pair-pixel in two stego images {P x , y , 1,  P x , y , 2} is classified into the embedded pixel or the non-embeddable pixel. If two pixels are greater than 2K – 1 or smaller than 256 – 2K – 1, then it is classified into the non-embeddable pixel. There is no secret bit in the non-embeddable pixel. In addition, the pixel is just the cover pixel. Other pixels between 2K – 1 and 256 – 2K – 1 are used to extract secret data and recover the cover image by the following procedures. The codebook with the size of 2K is generated in the same way as the dynamic encoding strategy. According to the pre-determined random value, the difference between pixels in two stego-images is calculated to obtain the embedded index, i.e.

$$ {I}_i^{\prime }=\left\{\begin{array}{l}{P}_{x, y,1}-{P}_{x, y,2},\kern0.5em \mathrm{if}\kern0.5em r=0,\\ {}{P}_{x, y,2}-{P}_{x, y,1},\kern0.5em \mathrm{if}\kern0.5em r=1.\end{array}\right. $$
(4)
Fig. 13
figure 13

Flowchart of data extraction and image recovery

Full size image

After obtaining the embedded value \( {I}_i^{\prime } \), the original index of the dynamic codeword can be derived by

$$ {I}_i=\left\{\begin{array}{l}2{I}_i^{\prime },\kern3em \mathrm{if}\kern0.5em {I}_i^{\prime}\ge 0,\\ {}2\times \left|{I}_i^{\prime}\right|-1,\kern0.5em \mathrm{otherwise}.\end{array}\right. $$
(5)

The codeword of the index I i is just the decimal representation of the set of K bits. Note that the index of the codeword needs to update from I i to 0 to ensure the validity of the codebook, and the indices of other codewords need to increase by 1. The above procedures are repeated until all messages have been decoded. Moreover, the mean of two stego-images is just the cover-image, i.e., \( {P}_{x, y}=\left\lceil \frac{P_{x, y,1}+{P}_{x, y,2}}{2}\right\rceil \). The above procedures can be illustrated further by the following algorithm.

  • Step 1: Generate one codebook.

  • Step 2: Classify a pixel-pair {P x , y , 1,  P x , y , 2} in two stego images into the embedded pixel-pair and the non-embedded pixel-pair. If both stego pixels belong to [2K – 1, 256 – 2K – 1], there is a secret digit between two pixels. The secret digit can be extracted correctly by the following steps. Otherwise, other pixels are label as the non-embedded pixels.

  • Step 3: According to the pre-determined random value and Eq. (4), the difference between pixels in two stego-images is calculated to obtain the embedded index.

  • Step 4: Recover the original index by Eq. (5).

  • Step 5: According to the original index, extract the codeword from the codebook.

  • Step 6: Transform the codeword into K secret bits.

  • Step 7: Recover the pixel by \( {P}_{x, y}=\left\lceil \frac{P_{x, y,1}+{P}_{x, y,2}}{2}\right\rceil \).

  • Step 8: Update the index of the codeword, i.e., modifying the index of the selected codeword from I i to 0 and increasing the index of the other codewords by 1.

  • Step 9: Perform the above steps for the next set of pixels until all secret bits have been extracted.

Figure 14 illustrates the above procedure. Let K = 3. The codebook with the size of 8 is generated to decode the embedded bits, where the initial values of codewords and their indices are set sequentially from 0 to 7. The decoding and recovery procedures are as follows. First of all, the difference between the two stego-images is calculated to extract the encoded indices {−4, 0, 1, 0}. All encoded indices can be decoded correctly by Eq. (5) to obtain the original indices. For example, the first encoded digit “–4” is decoded by I 1 = 2 × |−4| − 1 = 7. Its codeword is just the decimal representation of the three original bits, i.e., 710 = (111)2. Afterwards, the index of the codeword is updated from 7 to 0. In addition, the other indices are increased by 1 to assure the validity of the codebook. The pixel is recovered without any distortion, i.e., \( {P}_{1,1}=\left\lceil \frac{103+107}{2}\right\rceil =105 \)

Fig. 14
figure 14

Example of dynamic decoding and recovery

Full size image

The second encoded index is 0, and its original index is decoded by I 2 = 2 × 0 = 0. According to the index I 2 = 0, its codeword “7” in the updated codebook is transformed into the three original bits, i.e., 710 = (111)2. Since the index of the codeword is 0, we do not update the codebook. Finally, the second cover pixel is recovered losslessly by \( {P}_{1,2}=\left\lceil \frac{105+105}{2}\right\rceil =105 \). The procedures for decoding other digits and recovering other pixels are the same as the above procedures.

4 Experimental results

In this section, we compare the proposed method and four related methods in terms of the embedding rate and the visual quality of the stego-image, thereby confirming the effectiveness of the proposed method. The embedding rate ℜ was computed by

$$ \Re =\frac{\left\Vert S\right\Vert }{2\times \left\Vert {P}_{x, y}\right\Vert }\ \left(\mathrm{bpp}\right), $$
(6)

where bpp is bit per pixel; ‖S‖ is the number of embedded bits, and ‖P x , y ‖ is the number of original pixels.

The visual similarity between the stego-image and the cover-image was measured by the peak signal-to-noise ratio (PSNR)

$$ \mathrm{PSNR}=10\times { \log}_{10}\frac{255^2}{\mathrm{MSE}}\;\left(\mathrm{dB}\right),\mathrm{where}\;\mathrm{MSE}=\frac{1}{\left\Vert {P}_{x, y}\right\Vert}\sum_{x=1}^H\sum_{y=1}^W{\left({P}_{x, y}-{P}_{x, y, z}\right)}^2, $$
(7)

MSE is mean square error between the cover-image and the stego-image.

Figure 15 shows ten cover-images and five embedded images. Tables 1, 2 and 3 show the results of embedding different images into each cover-image. The embedding rate becomes greater as K increases. When the embedding rate is 2 bpp, the PSNR value of each stego-image can achieve 44 dB at least. This is because the proposed method can reduce the frequency of occurrence of the largest value and encode them as the smaller digits. In addition, the proposed method is very suitable for embedding the smooth image. For example, the PSNR values of two stego-images can maintain 52 dB after embedding the image “Google”.

Fig. 15
figure 15

Test images

Full size image
Table 1 Results of embedding the images “Logo” and “Dolphin” into different cover-images
Full size table
Table 2 Results of embedding the images “Google” and “IM” into different cover-images
Full size table
Table 3 Results of embedding the image “Brain” into different cover-images
Full size table

Figure 16 shows the comparison among the proposed method and the related methods [4, 7, 9, 11, 12, 15, 16]. Both our method and the CFS method decreases the embedded digit by 2K − 1, thus embedding these reduced digits into the image only needs to slightly modify pixels. The advantage implies that our method and the CFS method have better image quality than other methods. However, the CFS method cannot decrease the occurrence frequency of the maximum digits, that is why the PSNR values of Dolphin and Brain of the CFS-based hiding method are smaller than that of Lee and Huang’s method. Our method can decrease the embedded digits and the occurrence frequency of the maximum digits, thus the proposed method has better image quality than previous methods

Fig. 16
figure 16

Comparison among the proposed method and the seven related methods

Full size image

5 Conclusions

This paper proposed a dynamic encoding strategy to reduce the frequency of occurrence of the largest value, thereby decreasing the modification level in the data embedding stage. Experimental results showed that the PSNR value of the proposed method is greater than that of the CFS hiding method. In the future, we will analyze the correlation coefficient among the embedded bits in the complex images to further enhance the encoding performance.