<figure><img src="image_1.png" /></figure>

HAL
open science

# A Lossless Data Hiding Strategy Based on Two-Dimensional Side-Match Predictions

Chi-Yao Weng, Sheng-Jie Wang, Shiuh-Jeng Wang

► To cite this version:

Chi-Yao Weng, Sheng-Jie Wang, Shiuh-Jeng Wang. A Lossless Data Hiding Strategy Based on Two-Dimensional Side-Match Predictions. 3rd International Conference on Information and Communication Technology-EurAsia (ICT-EURASIA) and 9th International Conference on Research and Practical Issues of Enterprise Information Systems (CONFENIS), Oct 2015, Daejon, South Korea. pp.235-242, 10.1007/978-3-319-24315-3_24. [https://doi.org/10.1007/978-3-319-24315-3_24](https://doi.org/10.1007/978-3-319-24315-3_24)

HAL Id: hal-01466225

https://inria.hal.science/hal-01466225

Submitted on 13 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A lossless data hiding strategy based on two-dimensional side-match predictions

Chi-Yao Weng¹, Sheng-Jie Wang², Shiuh-Jeng WANG*

¹ Department of Computer Science, National Pingtung University, Pingtung 90004, TAIWAN

²,* Department of Information Management, Central Police University, Taoyuan 33304, TAIWAN

*whom correspondence: sjwang@mail.cpu.edu.tw

**Abstract.** The histogram-based reversible data hiding scheme (RDH) generated a one-dimensional (1D) histogram distribution. In this article, based on two-dimensional (2D) histogram distribution, a framework of reversible data hiding is proposed by using two side-match predictors, called as Forward side-match (FSM) and Backward side-match (BSM). First, by considering each predicted pixel value, we use two side-match predictors to obtain two prediction error distributions. A slope meter is computed by the differencing of two distributions. Then, a two dimensional histogram is generated by composing of BSM distribution and slope meter. Based on the 2D, more specified spaces can be found to enhance the performance. The experimental results demonstrated that our proposed scheme can achieve better performance in terms of both marked image quality and embedding capacity than that of conventional works.

**Keywords:** Reversible data hiding (RDH) scheme; Two dimensional histogram distribution; Side-match predictor

## 1 Introduction

Data hiding is an advanced technology for protecting the message with integrity and security from data transmission in a public network [1]. The secret information is capable of being hidden into some media, such as an image, audio or video data, using the well-known data hiding scheme. In general, for different target, the data hiding scheme can be classified into two categories. One is non-reversible data hiding scheme [2-4]. The non-reversible data hiding scheme aims to protect the hidden data for secret communication. The conventional LSBs (least signification bit substitution) is a simple and easy technology of non-reversible data hiding scheme. For example of 1-bit LSBs method, a secret bit is to be embedded into 1-rightmost bit of the cover pixel. The other is reversible data hiding (RDH) scheme [5-16]. The goal of RDH algorithm is to obtain both cover media and hidden data that can be recovered and extracted from stego media. It indicates that the distortion of cover media is intolerable.
ble when secret message is extracted. RDH can be widely applied into some
applications, such as military, medical, or legal document.

Many RDH techniques have been developed in present. It can be divided in-
to three categories, namely, histogram-based [5-8], difference expansion [9-
12], and prediction error [13-16]. Ni et al. first proposed a reversible data hid-
ing based on histogram shifting in 2006 [5]. In their method, the histogram
distribution is fist generated from an input image. After that, shift and conceal
the secret bits into the selected range from histogram distribution. Ni's ap-
proach performed a good quality in the stego image because pixel shifting and
data concealing are only shifted by one unit. Although histogram-based ap-
proach is simplicity and provides high image quality, the number of embed-
ding capacity is limited in the height of peak point. Later on, more efficient al-
gorithms have been invented for improving the embedding capacity limitation
[6-8].

The second category is difference expansion. In 2003, Tian proposed a re-
versible data hiding scheme based difference expansion (DE) [9]. Tain's
method expands the two pixel differencing for data concealing. The maximal
embedding ratio based on DE is near to 0.5 bpp (bit per pixel) for one layer
embedding. Some researchers are focused on investigation and developing
high-fidelity reversible data hiding scheme [10-12].

The histogram-based approach and difference expansion method can per-
form lossless data hiding, but their performance might be limited within the
media context. A basic idea is to review their drawback and develop suitable
strategy for promoting the performance in terms of embedding capacity and
image quality. The prediction error is a good strategy for both histogram-based
approach and difference expansion method to devise a new method of improv-
ing the performance. A local prediction reversible data hiding combined pre-
diction error and difference expansion is proposed by Drago and Coltur in
2014[13]. Drago and Colutr's approach utilized least square predictor to obtain
the prediction error, then, expend the prediction error for data hiding. This ap-
proach has better performance than that of DE method. Later on, more re-
searchers are developed the efficient approaches for obtaining higher perfor-
mance [14-16].

In reviewing above-mention reversible data hiding scheme, a framework of
reversible data hiding is proposed. Our main contribution is to build 2D histo-
gram distribution based on two side-match predictors and slope meter. 2D his-
togram distribution can collect more information and find out more spaces for
date embedding, resulting in high embedding capacity. Our proposed can be
extended into multi-dimensional framework in future.

The rest of the paper is organized as follows. The related works about histo-
gram shifting scheme are briefly introduced in Section 2. Section 3 presents
our proposed scheme in detail. The experimental result is illustrated in Section
4. Finally, the conclusion is concludes in Section 5.
## 2 Related works

In this subsection, we will review the reversible data hiding scheme based on histogram shifting. The histogram shifting scheme, named as histogram-based, is introduced in 2006. Ni et al.'s approach found out that each cover image has its pixel distribution. Firstly, they applied the statistic function to account each pixel number, the histogram distribution is thus generated. Next, find out the range of peak point and zero point from this distribution. In the end, shift and conceal the data into the range of peak point and zero point. The detail algorithm of histogram-based is shown as below.

**Input:** Cover image $CI$, each pixel value $x \in [0.255]$, secret message $SM=b_1b_2b_3...b_n, b_i \in \{0, 1\}$.

**Output:** Stego image $SI$, a pair information (peak point, zero point).

**Step 1:** Generate a histogram distribution $H(x)$ from an inputted image. Where, Figure 1 is an example of histogram distribution using Lena image.

**Step 2:** Find out a pair-data $(P, Z)$ from the histogram distribution. Notable, $P$ indicates the maximum number of pixels in this distribution. $Z$ means no pixel or minimum pixel in this distribution.

<figure><img src="image_3.png" /><figcaption>Figure 1. The example of pixel distribution using Lena as cover image</figcaption></figure>

**Step 3:** Shift all the pixels $x$ within the range of peak point and zero point by one unit. Note, the Figure 2 shows the result after pixel shifting operation. The shifting function is given as following.

$$ \begin{cases} x' = x + 1, & \text{if } Z > P \text{ and } x \in [P+1, Z] \\ x' = x - 1, & \text{if } P > Z \text{ and } x \in [Z, P-1] \end{cases} \tag{1} $$

<figure><img src="image_4.png" /><figcaption>Figure 2. The example of pixel shifting using Figure 1.</figcaption></figure>
Step 4: Scan all pixels in the cover image, once the pixel value meets the P value, and then, check the secret bits. If the secret bit is “0”, the pixel value remains unchanged. If the secret bit is “1”, the pixels value is changed by one unit according to following data concealing function

$$ \begin{cases} x' = x + 1, & \text{if } Z \ge P \\ x' = x - 1, & \text{if } P \ge Z \end{cases} \qquad (2) $$

Finally, output all the scanned pixel as the stego pixel (stego image). Notably, the stego pixel can be performed the processes of data extracting and pixel recovering since a pair-data (P, Z) is received. For the data extracting, the secret bit will be extracted when the inputted pixel meets the value of P or P+1. In other words, the hidden bits can be successfully retrieved. For the concept of pixel recovering, each inputted pixel can run the inverse of shifting operation to recover the pixel value as an original pixel.

## 3 Our proposed method

In this section, we introduce our reversible data hiding scheme based on 2D histogram modification in detail. The 1D histogram-based approach applied one factor, such as pixel value or prediction error, to generate a factor histogram distribution. Then, modify the highest value in the factor distribution for data concealing. For receiving more efficiency, our proposed scheme uses two prediction error to produce a 2D histogram distribution. More specified cases are to be considered for pursuing more spaces for promoting the embedding capacity. The detail of our data embedding algorithm is shown as below.

Input: Cover image CI with size M×N, CI = Iᵢⱼ, i= 0 to M-1, j= to N-1, secret message SMsg = b₁b₂b₃ ...bₙ, bᵢ ∈ {0, 1}.

Output: Marked-image MI, two pair information (PP₀, PZ₀) and (NP₀, NZ₀).

Step 1: Scan the cover image and run two side-match predictor methods, Forward side-match (FSM) and Backward side-match (BSM), to predict the pixel value in the image.

Step 1.1: The FSM prediction algorithm is shown the subsection, and then, compute the prediction error PE FSMᵢⱼ = PIᵢⱼ - Iᵢⱼ.

Step 1.1.a: If i = 0 and j = 0, then PIᵢⱼ = Iᵢⱼ - 128.

Step 1.1.b: If i = 0, then PIᵢⱼ = Iᵢⱼ - Iᵢⱼ-1.

Step 1.1.c: If j = 0, then PIᵢⱼ = Iᵢⱼ - Iᵢ-1ⱼ.

Step 1.1.d: Else, PIᵢⱼ = Iᵢⱼ - int(average (Iᵢ-1ⱼ + Iᵢ-1ⱼ-1 + Iᵢⱼ-1)).

Step 1.2: The Backward side-match (BSM) prediction algorithm is shown the subsection, and calculate the prediction error PE BSMᵢⱼ = PIᵢⱼ - Iᵢⱼ.

Step 1.2.a: If i = 0 and j = M-1, then PIᵢⱼ = Iᵢⱼ - 128.

Step 1.2.b: If i = 0, then PIᵢⱼ = Iᵢⱼ - Iᵢⱼ+1.

Step 1.2.c: If j = 0 and j ≠ 0, then PIᵢⱼ = Iᵢⱼ - Iᵢ-1ⱼ.
Step 1.2.d: Else, $PI_{i,j} = I_{i,j}$ - int (average $(I_{i-1,j} + I_{i,j-1})$).

Step 1.3: Obtain each slope meter SM from computing the difference of PE_BSM$_{i,j}$ and PE_FSM$_{i,j}$, where SM$_{i,j} = PE_FSM_{i,j} - PE_BSM_{i,j}$.

Step 2: Let (SM$_{i,j}$, PE_FSM$_{i,j}$) denotes a 2D value, and collect all 2D values to generate a 2D histogram distribution, H(SM$_{i,j}$, PE_FSM$_{i,j}$).

Step 3: Find two pair information (PP$_0$, PZ$_0$) and (NP$_0$, NZ$_0$) from 2D histogram distribution. Where a pair information (PP$_0$, PZ$_0$) is selected in the positive regions of 2D histogram distribution. In the same way, a pair information (NP$_0$, NZ$_0$) is picked by the negative positive regions of 2D histogram distribution.

Step 4: Shift all the prediction error PE_FSM$_{i,j}$ by 1 unit according to following function.

$$ PE\_FSM'_{i,j} = \begin{cases} PE\_FSM_{i,j} + 1, & PE\_FSM_{i,j} \in [PP_0 + 1, PZ_0] \\ PE\_FSM_{i,j} - 1, & PE\_FSM_{i,j} \in [NZ_0, NP_0 - 1] \end{cases} \quad (3) $$

Step 5: Scan all the PE_FSM$_{i,j}$ and fetch each secret bits from secret message SM$_{sg}$, and then, conceal the secret bitstring into PE_FSM$_{i,j}$ value while SM$_{i,j}$ precisely equals to “0” and the PE_FSM$_{i,j}$ equals to the peak values, PP$_0$ and NP$_0$. The data concealing function is listing as below.

$$ PE\_FSM'_{i,j} = \begin{cases} PE\_FSM_{i,j} + 1, & PE\_FSM_{i,j} = PP_0 \text{ and } b_i = 1 \\ PE\_FSM_{i,j}, & PE\_FSM_{i,j} = PP_0 \text{ and } b_i = 0 \\ PE\_FSM_{i,j}, & PE\_FSM_{i,j} = ZP_0 \text{ and } b_i = 0 \\ PE\_FSM_{i,j} - 1, & PE\_FSM_{i,j} = ZP_0 \text{ and } b_i = 1 \end{cases} \\ PE\_FSM'_{i,j} = \begin{cases} PE\_FSM_{i,j} + 1, & PE\_FSM_{i,j} = PP_0 \text{ and } b_i = 1 \\ PE\_FSM_{i,j}, & PE\_FSM_{i,j} = PP_0 \text{ and } b_i = 0 \\ PE\_FSM_{i,j}, & PE\_FSM_{i,j} = ZP_0 \text{ and } b_i = 0 \\ PE\_FSM_{i,j} - 1, & PE\_FSM_{i,j} = ZP_0 \text{ and } b_i = 1 \end{cases} \quad (4) $$

Step 6: Recover the marked prediction error value (PE_FSM$_{i,j}$) to be a stego-pixel (SPI) according the inverse of Forward side-match (FSM) predictor, where the inverse algorithm is given as below.

Step 6.1: If $i=0$ and $j=0$, then $SPI_{i,j} = PE\_FSM_{i,j} + 128$.

Step 6.2: If $i=0$, then $SPI_{i,j} = PE\_FSM_{i,j} + I_{i,j-1}$.

Step 6.3: If $j=0$, then $SPI_{i,j} = PE\_FSM_{i,j} + I_{i-1,j}$.

Step 6.4: Else, $SPI_{i,j} = PE\_FSM_{i,j} + \text{int}(\text{average}(I_{i-1,j} + I_{i-1,j-1} + I_{i,j-1}))$.

All the marked prediction error values are fully to be recovered, the marked image (MI) is therefore outputted.

The data extracting procedure is similar with the data embedding procedure. Two prediction methods, FSM and BSM, are also used in the extracting process. The extracting process is the inverse of the data embedding procedure.
After running the data extracting procedure, the secret message is completely obtained and the image is successfully recovered.

## 4 Experiment results

In section, we demonstrate the simulations of our proposed scheme. Five 512×512 images, including Lena, Airplane, Pepper, Boat, and Goldhill (See Figure 3) are used in our simulations. The secret bitstring in our simulation is generated by the random number generator. We also employ the commonly measure function peak-signal-to-noise-ratio (PSNR) and MSE as a evaluate tool for comparing the visual quality between the cover image and marked image. The measure functions are given as following.

$$PSNR(db) = 10 \times \log_{10}\left(\frac{Max^2}{MSE}\right) \qquad (8)$$

$$MSE = \frac{1}{W \times H} \sum_{x=1}^{W} \sum_{y=1}^{H} ((I(x, y)) - (I'(x, y)))^2 \qquad (9)$$

where W and H are defined as the width and height of the image. I(x, y) and I'(x, y) indicates the values of cover image and marked image, respectively. The Max means the maximum value of cover image. Here, our cover image is gray level image, thus, the Max value in gray level is 255(=2⁸).

<figure><img src="image_5.png" /><figcaption>Figure 3. The five cover images. (a)Lena; (b)Airplane; (c)Pepper; (d)Boat; (e)Goldhill</figcaption></figure>

To obtain a better knowledge of how different cover image impact the performance of the proposed RDH scheme, we compare our experimental results with the recent RDH scheme, the comparison result is illustrated in Table 1. From this comparison, our scheme has better performance in terms of high embedding capacity and good image quality than that of existing RDH methods. The side match predictor applied the neighbor pixels to predict the predictions.
tion value. Generally speaking, in a nature image, the current pixel is very similar with its neighbor pixels. Assume that we use side match manner to predict the value, we can obtain an accuracy prediction. It leads that more and more prediction errors are falling into zero space. This is a reason that our side match predictor explores the advantage of prediction error to create more space for data concealing.

<table><caption>Table 1. The performance comparison with various approaches</caption><thead><tr><th></th><th>Ni et al.'s [5]</th><th>Tsai et al.'s[7]</th><th>Li et al.'s [14]</th><th>Our approach</th></tr></thead><tbody><tr><td>Lean</td><td>0.02</td><td>0.18</td><td>0.23</td><td>0.25</td></tr><tr><td>Airplane</td><td>0.07</td><td>0.25</td><td>0.30</td><td>0.29</td></tr><tr><td>Pepper</td><td>0.02</td><td>0.18</td><td>0.24</td><td>0.23</td></tr><tr><td>Boat</td><td>0.04</td><td>0.17</td><td>0.19</td><td>0.22</td></tr><tr><td>Goldhill</td><td>0.02</td><td>0.13</td><td>0.19</td><td>0.17</td></tr><tr><td>Avag. Capacity (bpp)</td><td>0.034</td><td>0.182</td><td>0.230</td><td>0.232</td></tr><tr><td>Avag. PSNR (db)</td><td>48.30</td><td>48.7+</td><td>48.47</td><td>49.32</td></tr></tbody></table>

# 5 Conclusion

In this paper, based on two side match predictors and two peaks histogram embedding, an efficient reversible data hiding scheme is proposed. The key point is to build 2D histogram based on two side match predictors and slope meter. The slope meter is used to estimate the differencing of two prediction errors. Based on accurate prediction and selecting two peak points, our proposed scheme provides more spaces for enhancing embedding capacity, the evidence can be seen in the performance evaluation. From the experimental result, it shows that our proposed approach is superior over some histogram-based works.

# Acknowledgment

This work was supported in part by the Ministry of Science and Technology, Taiwan, under Contract MOST 103-2221-E-015-002- and MOST 104-2221-E-015-001-.

# References

1. Bender W, Gruhl D, Morimote N, Lu A. Techniques for data hiding. IBM Systems Journal 1996; 35(3-4):313-316.

2. Chan CK, Chen LM. Hiding data in images by simple LSB substitution. Pattern Recognition 2004; 37(3):469-474.
3. Sun HM, Weng CY, Wang SJ, Yang CH. Data embedding in image-media using weight-function on modulo operation. ACM Trans. on Embedded Computing Systems 2013; 12(2):1-12.

4. Maleki N, Jalail M, Jahan MV. Adaptive and non-adaptive data hiding methods for gray-scale images based on modulus function. Egyptian Informatics Journal 2014; 15(2):115-127.

5. Ni ZC, Shi YQ, Ansari N, Su W. Reversible data hiding. IEEE Trans. on Circuits and Systems for Video Technology 2006; 16(3): 354-362.

6. Tai WL, Yeh CM, Chang CC. Reversible data hiding based on histogram modification of pixel differences. IEEE Trans. on Circuits and Systems for Video Technology 2009; 19(6): 906-910.

7. Tsai P, Hu YC, Yeh HL. Reversible image hiding scheme using predictive coding and histogram shifting. Signal Processing 2009; 89(6): 1129-1143.

8. Tain J. Reversible data embedding using a difference expansion. IEEE Trans. on Circuits and Systems for Video Technology 2003; 13(8): 890-896.

9. Kim HJ, Sachnev V, Shi YQ, Nam J, Choo HG. A novel difference expansion transform for reversible data embedding. IEEE Trans. On Information Forensics and Security 2008; 3(3): 456-465.

10. Alattar M. Reversible watermark using the difference expansion of a generalized integer transform. IEEE Trans. On Image Processing 2004; 13(8): 1147-1156.

11. Sachnev, Kim HJ, Nam J, Suresh S, Shi YQ. Reversible watermarking algorithm using sorting and prediction. IEEE Trans. on Circuits and Systems for Video Technology 2009; 19(7): 989-999.

12. Wu HC, Lee CC, Tsai CS, Chu YP, Chen HR. A high capacity reversible data hiding scheme with edge prediction and difference expansion. The Journal of Systems and Software 2009; 82(12):1966-1973

13. Dragoi I, Coltuc D. Local-prediction-based difference expansion reversible watermarking. IEEE Trans. on Image Processing 2014; 23(4): 1779-1790.

14. Li X, Yang B, Zeng T. Efficient reversible watermarking based on adaptive prediction-error expansion and pixel selection. IEEE Trans. on Image Processing 2011; 20(12): 3524-3533.

15. Yang, CH, Tsai, MH. Improving histogram-based reversible data hiding by interleaving predictions. IET Image Processing 2010; 4(4):223-234.

16. Wang, SY, Li, CY, Kuo, WC. Reversible data hiding based on two-dimensional prediction errors. IET Image Processing 2013; 7(9):805-816.