# Histogram Modification and Wavelet Transform for High Performance Watermarking

Authors: Ying-Shen Juang; Lu-Ting Ko; Jwu-E Chen; Yaw-Shih Shieh; Tze-Yun Sung; Hsi Chin Hsin
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

This paper proposes a reversible watermarking technique for natural images. According to the similarity of neighbor coefficients’ values in wavelet domain, most differences between two adjacent pixels are close to zero. The histogram is built based on these difference statistics. As more peak points can be used for secret data hiding, the hiding capacity is improved compared with those conventional methods. Moreover, as the differences concentricity around zero is improved, the transparency of the host image can be increased. Experimental results and comparison show that the proposed method has both advantages in hiding capacity and transparency.


---

## Body

## 1. Introduction

Digital watermarking is a technique to embed imperceptible, important data called watermark into the host image for the purpose of copyright protection, integrity check, and/or access control [1–9]. However, it might cause the distortion problem regarding the recovery of the original host image. In order to protect the host image from being distorted, a reversible watermarking technique has been reported in the literature. The reversible watermarking technique does not only hide the secret data but also the host image that can be exactly reconstructed in a decoder. Therefore, it can be used in those applications where the host images, such as medical images, military maps, and remote sensing images, must be completely recovered [10–14].Recent reversible watermarking techniques can be divided into spatial domain, transform domain, and compressed domain methods. In spatial domain based methods [15–19], the secret data is embedded by pixels’ value modification. In the transform domain methods [20, 21], reversible-guaranteed transforms, such as integer discrete cosine transform and integer wavelet transform, are exploited and data embedding is depending on coefficient modulation. In the compressed domain methods [22, 23], image compression techniques like vector quantization and block truncation coding are involved.Most spatial domain reversible watermarking techniques are developed based on three principles, they are difference expansion [15, 16] and histogram modification [17–19, 24]. Zhao et al. proposed a reversible data hiding based on multilevel histogram modification [19]. In this scheme, the inverse “S” order is adopted to scan the image pixels for difference generation. The embedding capacity is determined by two factors, the embedding level and the number of histogram bins around 0. However, with a better pixel scan path can provide a higher capacity with the embedding level not changing.Wavelet transform provides an efficient multiresolution representation with various desirable properties such as subband decompositions with orientation selectivity and joint space-spatial frequency localization. In wavelet domain, the higher detailed information of a signal is projected onto the shorter basis function with higher spatial resolution; the lower detailed information is projected onto the larger basis function with higher spectral resolution. This matches the characteristics of a better situation for scaning the image pixels for difference generation [25, 26].In this paper, we propose a reversible watermarking technique based on histogram modification and discrete wavelet transform. The remainder of the paper proceeds as follows. In Section2, the reversible watermarking based on histogram modification is reviewed briefly. Section 3 describes the reversible watermarking based on histogram modification and discrete wavelet transform. Experimental results and comparison are presented in Section 4. Finally, conclusion is given in Section 5.


## 2. Histogram Modification for Reversible Watermarking

Zhao et al. proposed a reversible data hiding based on histogram modification in [19]. In this scheme, the inverse “S” order is adopted to scan the image pixels for difference generation. The integer parameter called embedding level EL (EL≥0) controls the hiding capacity and transparency of the marked image. A higher EL indicates that more watermark can be embedded but leads more distortion to a watermarked image.The data embedding process ofEL=0 is as follows, and the histogram modification strategy is shown in Figure 1. First, the image is inverse “S” scanned and the difference histogram is constructed. Next, the histogram shifting is performed. The secret bit “1” can be hidden by changing the difference of the pixel value from 0 to 1, and the “0” is hidden by keeping the difference of the pixel value not changed. Each marked pixel can be produced by its left neighbor subtracting the modified difference. Finally, rearrange these marked pixels to produce the watermarked image.The histogram modification strategy: (a) the original histogram and (b) the histogram shifting: shift bins larger than 0 rightward (orange bins). (c) Secret data embedding: embed secret data “0” by keeping the difference of the pixel value not changed (blue bin) and embed secret data “1” by changing the difference of the pixel value from 0 to 1 (red bin). (d) The modified histogram.
(a)
(b)
(c)
(d)The process of data extraction and image recovery is as follows. The watermarked image is also inverse “S” scanned into a sequence first. As the first pixel value is not changed during embedding, we have the first pixel value. Second, the difference of the first pixel value and second pixel value can be obtained. If the difference is 0, one bit watermark “0” is extracted. If the difference is 1, one bit watermark “1” is extracted and the original difference is 0. Thus the original pixel associated with the difference can be obtained. If the difference is larger than 1, subtract 1 from the difference and recover the original pixel. Repeat these operations for the remained watermarked sequence and all the host pixels are recovered. Finally, rearrange these recovered pixels to produce the original host image.The embedding capacity is determined by two factors, the embedding level and the number of histogram bins around 0. As mentioned before, a higherEL indicates that more watermark can be embedded, but leads more distortion to a watermarked image. However, with a better pixel scan path can provide a higher capacity with the embedding level not changing. Thus, we proposed an appropriate method to reach a higher capacity with embedding level EL=0.


## 3. The Proposed Method

In this section, we proposed a novel reversible data hiding based on histogram modification and discrete wavelet transform. According to the similarity of neighbor coefficients’ values in wavelet domain, most differences between two adjacent pixels are close to zero. The histogram is built based on these difference statistics. As more peak points can be used for secret data hiding, the hiding capacity is improved compared with those conventional methods.


### 3.1. Discrete Wavelet Transform

Discrete wavelet transform (DWT) provides an efficient multiresolution analysis for signals, specifically, any finite energy signalf(x) can be written by
(3.1)f(x)=∑nSJ(n)ϕJn(x)+∑ℓ≤J∑nDℓ(n)ψℓn(x),
where ℓ denotes the resolution index with larger values meaning coarser resolutions, n is the translation index, ψ(x) is a mother wavelet, ϕ(x) is the corresponding scaling function, ψℓn(x)=2-ℓ/2ψ(2-ℓx-n), ϕℓn(x)=2-ℓ/2ϕ(2-ℓx-n), SJ(n) is the scaling coefficient representing the approximation information of f(x) at the coarsest resolution 2J, and Dℓ(n) is the wavelet coefficient representing the detail information of f(x) at resolution 2ℓ. Coefficients Sℓ(n) and Dℓ(n) can be obtained from the scaling coefficient Sℓ-1(n) at the next finer resolution 2ℓ-1 by using 1-level DWT, which is given by
(3.2)Sℓ(n)=∑kSℓ-1(k)h(2n-k),Dℓ(n)=∑kSℓ-1(k)g(2n-k),
where h(n)=〈ϕ,ϕ-1,-n〉, g(n)=〈ψ,ϕ-1,-n〉, and 〈·,·〉 denote the inner product. It is noted that h(n) and g(n) are the corresponding low-pass filter and high-pass filter, respectively. Moreover, Sℓ-1(n) can be reconstructed from Sℓ(n) and Dℓ(n) by using the inverse DWT, which is given by
(3.3)Sℓ-1(n)=∑kSℓ(k)h~(n-2k)+∑kDℓ(k)g~(n-2k),
where h~(n)=h(-n) and g~(n)=g(-n).For image applications, 2D DWT can be obtained by using the tensor product of 1D DWT. Among wavelets, Haar’s wavelet is the simplest one, which has been widely used for many applications. The low-pass filter and high-pass filter of Haar’s wavelet are as follows(3.4)h(0)=0.5;h(1)=0.5,g(0)=0.5;g(1)=-0.5.
Figures 2 and 3 show the row decomposition and the column decomposition using Haar’s wavelet, respectively. Notice that the column decomposition may follow the row decomposition, or vice versa, in 2D DWT.Figure 2
The row decomposition using Haar’s wavelet (A, B, C, and D are pixels values).Figure 3
The column decomposition using Haar’s wavelet (E, F, G, and Hare pixel values).As a result, 2D DWT with Haar’s wavelet is as follows:(3.5)LL=A+B+C+D4,LH=A+B-C-D4,HL=A-B+C-D4,HH=A-B-C+D4,
where A, B, C, and D are pixels values, and LL, LH, HL, and HH denote the approximation, detail information in the horizontal, and vertical and diagonal orientations, respectively, of the input image. Figure 4 shows 1-level, 2D DWT using Haar’s wavelet.Figure 4
1-level 2D DWT using Haar’s wavelet (A, B, C, and D are pixel values).TheLL subband of an image can be further decomposed into four subbands: LLLL, LLLH, LLHL, and LLHH at the next coarser resolution, which together with LH, HL, and HH forms the 2-level DWT of the input image. Thus, higher level DWT can be obtained by decomposing the approximation subband in the recursive manner.


### 3.2. Watermarking Scheme

Figure5 shows the proposed embedding process; the details are described below. First, decompose the host M×N image I via 2D DWT into four 1-level subbands: LL, LH, HL, and HH. Then decompose these 1-level subbands again into sixteen 2-level subbands: LLLL, LLLH, LLHL, LLHH, LHLL, LHLH, LHHL, LHHH, HLLL, HLLH, HLHL, HLHH, HHLL, HHLH, HHHL, and HHHH, as shown in Figures 5(a) and 5(b). Second, generate a random sequence for these subbands. Third, select a random starting location in the first subbands. Fourth, pick a random scanning direction and scan the first subband into pixel sequence p1,p2,…,pM×N/16. Next, compute the difference di (1≤i≤M×N/16) according to (3.6) and construct a histogram based on di (2≤i≤M×N/16)
(3.6)di={p1,i=1,pi-1-pi,2≤i≤M×N/16.
Then shift the histogram bins which are larger than 1 rightward one level as
(3.7)di′={p1,ifi=1,di,ifdi<1,2≤i≤M×N/16,di+1,ifdi≥1,2≤i≤M×N/16.
Examine di′=0  (2≤i≤M×N/16) one by one. Each difference less than 1 can be used to hide one secret bit (pixels with green color in Figure 5(f) of the difference sequence di′). If the corresponding watermark bit w=0, it is not changed (pixels with blue color in Figure 5(f) of the difference sequence di′′). And if w=1, add the difference by 1 (pixels with red color in Figure 5(f) of the difference sequence di′′). The operation is as
(3.8)di′′={p1,ifi=1,di′+w,ifdi′<1,w=1,2≤i≤M×N/16,di′,ifdi′<1,w=0,2≤i≤M×N/16,di′,ifdi′≥1,2≤i≤M×N/16,
and generate watermarked pixel sequence pi′ by this operation:
(3.9)pi′={p1,i=1,pi-1-di′′,2≤i≤M×N/16.
Rearrange pi′ and the first 2-level watermarked subband is obtained. Repeat these operations for the remained subbands.The proposed data embedding principle: (a) the original host image (b) decomposes into sixteen subbands, (c) generates the random sequence of the subbands, (d) selects the random starting location and direction of each subbands (e) An example of embedding watermark into pixel sequence; (f) rearranged watermarked subbands; (g) the watermarked image.
(a)
(b)
(c)
(d)
(e)
(f)
(g)Pick the 2-level watermarked subbandsLLLL′, LLLH′, LLHL′, and LLHH′ and perform the 2D inverse DWT to get the 1-level watermarked subband LL′. Repeat this operation for the remained 2-level watermarked subbands to get the 1-level watermarked subbands LH′, HL′, and HH′. Finally, perform the 2D inverse DWT to get the watermarked image I′.The data extraction and image recovery is the inverse process of data embedding, and the process is as follows. First, decompose the watermarked imageI′ via 2D DWT into four 1-level watermarked subbands: LL′, LH′, HL′, and HH′. Then decompose these watermarked subbands again into sixteen 2-level watermarked subbands: LLLL′, LLLH′, LLHL′, LLHH′, LHLL′, LHLH′, LHHL′, LHHH′, HLLL′, HLLH′, HLHL′, HLHH′, HHLL′, HHLH′, HHHL′, and HHHH′. Second, get the subband sequence of the watermark, starting location, and scanning direction of each watermarked subbands. Third, scan the first watermarked subband into watermarked pixel sequence p1′,p2′,…,pM×N/16′. Then recover the original pixel sequence based on the following:
(3.10)pi={p1′,ifi=1,pi′,ifpi-1-pi′≤1,2≤i≤M×N,pi′-1,ifpi-1-pi′>1,2≤i≤M×N.
Figure 6 shows an example of secret data extracting and original pixel sequence recovering.Figure 6
An example of secret data extracting and original pixel sequence recovering.Rearrange the original pixel sequence and the original 2-level subband can be recovered. Repeat those operations until all 2-level subbands are recovered and perform 2D inverse DWT to get the 1-level subbands. Finally, perform 2D inverse DWT again and the original host image can be obtained.The secret data is extracted as(3.11)w={0,if0≤pi-1-pi′<1,2≤i≤M×N,1,if1≤pi-1-pi′<2,2≤i≤M×N.
Rearrange these extracted bits and the original watermark can be obtained.


## 3.1. Discrete Wavelet Transform

Discrete wavelet transform (DWT) provides an efficient multiresolution analysis for signals, specifically, any finite energy signalf(x) can be written by
(3.1)f(x)=∑nSJ(n)ϕJn(x)+∑ℓ≤J∑nDℓ(n)ψℓn(x),
where ℓ denotes the resolution index with larger values meaning coarser resolutions, n is the translation index, ψ(x) is a mother wavelet, ϕ(x) is the corresponding scaling function, ψℓn(x)=2-ℓ/2ψ(2-ℓx-n), ϕℓn(x)=2-ℓ/2ϕ(2-ℓx-n), SJ(n) is the scaling coefficient representing the approximation information of f(x) at the coarsest resolution 2J, and Dℓ(n) is the wavelet coefficient representing the detail information of f(x) at resolution 2ℓ. Coefficients Sℓ(n) and Dℓ(n) can be obtained from the scaling coefficient Sℓ-1(n) at the next finer resolution 2ℓ-1 by using 1-level DWT, which is given by
(3.2)Sℓ(n)=∑kSℓ-1(k)h(2n-k),Dℓ(n)=∑kSℓ-1(k)g(2n-k),
where h(n)=〈ϕ,ϕ-1,-n〉, g(n)=〈ψ,ϕ-1,-n〉, and 〈·,·〉 denote the inner product. It is noted that h(n) and g(n) are the corresponding low-pass filter and high-pass filter, respectively. Moreover, Sℓ-1(n) can be reconstructed from Sℓ(n) and Dℓ(n) by using the inverse DWT, which is given by
(3.3)Sℓ-1(n)=∑kSℓ(k)h~(n-2k)+∑kDℓ(k)g~(n-2k),
where h~(n)=h(-n) and g~(n)=g(-n).For image applications, 2D DWT can be obtained by using the tensor product of 1D DWT. Among wavelets, Haar’s wavelet is the simplest one, which has been widely used for many applications. The low-pass filter and high-pass filter of Haar’s wavelet are as follows(3.4)h(0)=0.5;h(1)=0.5,g(0)=0.5;g(1)=-0.5.
Figures 2 and 3 show the row decomposition and the column decomposition using Haar’s wavelet, respectively. Notice that the column decomposition may follow the row decomposition, or vice versa, in 2D DWT.Figure 2
The row decomposition using Haar’s wavelet (A, B, C, and D are pixels values).Figure 3
The column decomposition using Haar’s wavelet (E, F, G, and Hare pixel values).As a result, 2D DWT with Haar’s wavelet is as follows:(3.5)LL=A+B+C+D4,LH=A+B-C-D4,HL=A-B+C-D4,HH=A-B-C+D4,
where A, B, C, and D are pixels values, and LL, LH, HL, and HH denote the approximation, detail information in the horizontal, and vertical and diagonal orientations, respectively, of the input image. Figure 4 shows 1-level, 2D DWT using Haar’s wavelet.Figure 4
1-level 2D DWT using Haar’s wavelet (A, B, C, and D are pixel values).TheLL subband of an image can be further decomposed into four subbands: LLLL, LLLH, LLHL, and LLHH at the next coarser resolution, which together with LH, HL, and HH forms the 2-level DWT of the input image. Thus, higher level DWT can be obtained by decomposing the approximation subband in the recursive manner.


## 3.2. Watermarking Scheme

Figure5 shows the proposed embedding process; the details are described below. First, decompose the host M×N image I via 2D DWT into four 1-level subbands: LL, LH, HL, and HH. Then decompose these 1-level subbands again into sixteen 2-level subbands: LLLL, LLLH, LLHL, LLHH, LHLL, LHLH, LHHL, LHHH, HLLL, HLLH, HLHL, HLHH, HHLL, HHLH, HHHL, and HHHH, as shown in Figures 5(a) and 5(b). Second, generate a random sequence for these subbands. Third, select a random starting location in the first subbands. Fourth, pick a random scanning direction and scan the first subband into pixel sequence p1,p2,…,pM×N/16. Next, compute the difference di (1≤i≤M×N/16) according to (3.6) and construct a histogram based on di (2≤i≤M×N/16)
(3.6)di={p1,i=1,pi-1-pi,2≤i≤M×N/16.
Then shift the histogram bins which are larger than 1 rightward one level as
(3.7)di′={p1,ifi=1,di,ifdi<1,2≤i≤M×N/16,di+1,ifdi≥1,2≤i≤M×N/16.
Examine di′=0  (2≤i≤M×N/16) one by one. Each difference less than 1 can be used to hide one secret bit (pixels with green color in Figure 5(f) of the difference sequence di′). If the corresponding watermark bit w=0, it is not changed (pixels with blue color in Figure 5(f) of the difference sequence di′′). And if w=1, add the difference by 1 (pixels with red color in Figure 5(f) of the difference sequence di′′). The operation is as
(3.8)di′′={p1,ifi=1,di′+w,ifdi′<1,w=1,2≤i≤M×N/16,di′,ifdi′<1,w=0,2≤i≤M×N/16,di′,ifdi′≥1,2≤i≤M×N/16,
and generate watermarked pixel sequence pi′ by this operation:
(3.9)pi′={p1,i=1,pi-1-di′′,2≤i≤M×N/16.
Rearrange pi′ and the first 2-level watermarked subband is obtained. Repeat these operations for the remained subbands.The proposed data embedding principle: (a) the original host image (b) decomposes into sixteen subbands, (c) generates the random sequence of the subbands, (d) selects the random starting location and direction of each subbands (e) An example of embedding watermark into pixel sequence; (f) rearranged watermarked subbands; (g) the watermarked image.
(a)
(b)
(c)
(d)
(e)
(f)
(g)Pick the 2-level watermarked subbandsLLLL′, LLLH′, LLHL′, and LLHH′ and perform the 2D inverse DWT to get the 1-level watermarked subband LL′. Repeat this operation for the remained 2-level watermarked subbands to get the 1-level watermarked subbands LH′, HL′, and HH′. Finally, perform the 2D inverse DWT to get the watermarked image I′.The data extraction and image recovery is the inverse process of data embedding, and the process is as follows. First, decompose the watermarked imageI′ via 2D DWT into four 1-level watermarked subbands: LL′, LH′, HL′, and HH′. Then decompose these watermarked subbands again into sixteen 2-level watermarked subbands: LLLL′, LLLH′, LLHL′, LLHH′, LHLL′, LHLH′, LHHL′, LHHH′, HLLL′, HLLH′, HLHL′, HLHH′, HHLL′, HHLH′, HHHL′, and HHHH′. Second, get the subband sequence of the watermark, starting location, and scanning direction of each watermarked subbands. Third, scan the first watermarked subband into watermarked pixel sequence p1′,p2′,…,pM×N/16′. Then recover the original pixel sequence based on the following:
(3.10)pi={p1′,ifi=1,pi′,ifpi-1-pi′≤1,2≤i≤M×N,pi′-1,ifpi-1-pi′>1,2≤i≤M×N.
Figure 6 shows an example of secret data extracting and original pixel sequence recovering.Figure 6
An example of secret data extracting and original pixel sequence recovering.Rearrange the original pixel sequence and the original 2-level subband can be recovered. Repeat those operations until all 2-level subbands are recovered and perform 2D inverse DWT to get the 1-level subbands. Finally, perform 2D inverse DWT again and the original host image can be obtained.The secret data is extracted as(3.11)w={0,if0≤pi-1-pi′<1,2≤i≤M×N,1,if1≤pi-1-pi′<2,2≤i≤M×N.
Rearrange these extracted bits and the original watermark can be obtained.


## 4. Experimental Results

Figure7 shows our test images, six 256×256 with 256 gray levels are selected as test images; they are Lena, Baboon, Barbara, Boat, Board, and Peppers. Table 1 lists the average capacity (bit per pixel) and PSNR (db) values of the proposed scheme. The peak signal to noise ratio (PSNR) is used to evaluate the image quality [27], which is defined as
(4.1)PSNR=20log(255MSE),
where MSE denotes the mean square error.Table 1
Performance comparison of Zhao et al.’s method and the proposed method.
Test images
Items
Zhao et al. [19]
This work
Lena
Capacity
0.1257
0.1511
PSNR (dB)
50.65
69.51
Baboon
Capacity
0.0329
0.0847
PSNR (dB)
51.01
60.86
Barbara
Capacity
0.0604
0.1069
PSNR (dB)
50.91
69.81
Boat
Capacity
0.0858
0.1186
PSNR (dB)
50.79
72.39
Board
Capacity
0.0547
0.0702
PSNR (dB)
50.92
55.11
Peppers
Capacity
0.1113
0.1371
PSNR (dB)
54.12
66.41Test images: (a) Lena, (b) Baboon, (c) Barbara, (d) Boat, (e) Board, and (f) Peppers. The six watermarked images obtained by our scheme and Zhao et al.’s method are shown in Figures8–13. Note that all of the bits of the watermarks embedded inside are “1” which leads to a maximum distortion. All these results demonstrate not only the capacities but also the PSNRs in our method which are improved. In other words, even though more secret data embedded in our scheme and leads more distortion, the marked images quality is still better.
(a)
(b)
(c)
(d)
(e)
(f)The six watermarked images obtained by our scheme and Zhao et al.’s method are shown in Figures8, 9, 10, 11, 12, and 13. Note that all of the bits of the watermarks embedded inside are “1” which leads to a maximum distortion. All these results demonstrate that not only the capacities but also the PSNRs in our method are improved. In other words, even though more secret data embedded in our scheme and leads more distortion, the marked images quality is still better.Watermarked Lena image obtained by our scheme ((a) 10580 bits hidden, 69.51 dB) and Zhao et al.’s scheme ((b) 8239 bits hidden, 50.65 dB) withEL=0.
(a)
(b)Watermarked Baboon’s image obtained by our scheme ((a) 5900 bits hidden, 60.86 dB) and Zhao et al.’s scheme ((b) 2161 bits hidden, 51.01 dB) withEL=0.
(a)
(b)Watermarked Barbara’s image obtained by our scheme ((a) 7446 bits hidden, 69.81 dB) and Zhao et al.’s scheme ((b) 3959 bits hidden, 50.91 dB) withEL=0.
(a)
(b)Watermarked Boat image obtained by our scheme ((a) 8257 bits hidden, 72.39 dB) and Zhao et al.’s scheme ((b) 5628 bits hidden, 50.79 dB) withEL=0.
(a)
(b)Watermarked Board image obtained by our scheme ((a) 4888 bits hidden, 55.11 dB) and Zhao et al.’s scheme ((b) 3589 bits hidden, 50.92 dB) withEL=0.
(a)
(b)Watermarked Peppers image obtained by our scheme ((a) 9456 bits hidden, 66.41 dB) and Zhao et al.’s scheme ((b) 7299 bits hidden, 54.12 dB) withEL=0.
(a)
(b)


## 5. Conclusion

In this paper, a reversible watermarking based on the histogram modification has been proposed. The transparency of the watermarked image can be increased by taking advantage of the proposed watermarking. As the host image can be exactly reconstructed, it is suitable especially for medical images, military maps, and remote sensing images. The proposed reversible watermarking based on multilevel histogram modification and discrete wavelet transform is preferable and provides a higher capacity and higher transparency compared with other histogram modification based methods.



---

*Source: 164869-2012-11-10.xml*