# A New Information Hiding Method Based on Improved BPCS Steganography

Authors: Shuliang Sun
Journal: Advances in Multimedia
 (2015)

---

## Abstract

Bit-plane complexity segmentation (BPCS) steganography is advantageous in its capacity and imperceptibility. The important step of BPCS steganography is how to locate noisy regions in a cover image exactly. The regular method, black-and-white border complexity, is a simple and easy way, but it is not always useful, especially for periodical patterns. Run-length irregularity and border noisiness are introduced in this paper to work out this problem. Canonical Cray coding (CGC) is also used to replace pure binary coding (PBC), because CGC makes use of characteristic of human vision system. Conjugation operation is applied to convert simple blocks into complex ones. In order to contradict BPCS steganalysis, improved BPCS steganography algorithm adopted different bit-planes with different complexity. The higher the bit-plane is, the smaller the complexity is. It is proven that the improved BPCS steganography is superior to BPCS steganography by experiment.


---

## Body

## 1. Introduction

Steganography is an art and science of invisible communication. It comes from Greek for covered writing and essentially means “to hide in plain sight” [1]. Embedding capacity, security (imperceptibility), and robustness are the most important three features in steganographic system. Generally speaking, there is a fundamental compromise between embedding capacity and security in information hiding scheme. Steganography methods can be divided into two categories: original (spatial) domain methods and transform domain methods. Cover image is transformed into frequency domain first, and then the secret messages are embedded in the coefficients of transformed cover image. Singh et al. [2] proposed a method to combine two techniques. One was image enhancement and the other was image steganography based on DFT. Kaur and Kochhar [3] provided a technique for image steganography based on DCT. The algorithm had good invisibility and security. A three-level DWT decomposition was done on host image and secret information was hidden in approximation coefficients of the decomposed image in [4]. The stegoimage is subjected to image processing attacks. Abu et al. [5] discussed a robust algorithm, which was based on integer Haar wavelet transform and pixel value difference. Ramezani et al. [6] gave a steganography method in contourlet domain. The optimal pixel adjustment process and genetic algorithm are also used. Alsaif and Saalih [7] presented a data hiding technique in NSCT domain. Secret data was embedded in high frequency directional band pass of contourlet transform. In spatial domain methods, the processing is applied on the image pixel values directly. Least significant bits (LSB) substitution [8] is the most well-known spatial steganographic system. Although this method is simple and easy, it is weak in robustness and compression, such as JPEG compression. Soumi et al. [9] presented a mosaic image steganography based on genetic algorithms for enhanced security. Mandal and Das [10] proposed a color image steganography method based on pixel value differencing. Secret data was hiding in the component of a pixel in a color image. Arora and Anand [11] gave an approach for image steganography using edge detection method. In their study, edges of RGB image were detected by scanning method using 3∗3 window. Since human eyes are not sensitive to tiny alterations of noisy data, it will not be noticed when the data in noisy regions is replaced with another noisy data. That is bit-plane complexity segmentation steganography (BPCS steganography) [12].


## 2. The Principle of BPCS Steganography

BPCS steganography was first put forward by Kawaguchi and Eason [13]. The basic principle is that firstly cover image is divided into “informative region” and “noise-like region.” Then the secret information is hidden in noise-like blocks of cover image [14]. In LSB technique, data is hidden in the lowest bit-plane. But in BPCS technique, data is hidden in pixel blocks of all the planes, from the highest plane (most significant bit, MSB plane) to the lowest plane (LSB plane), which have noisy patterns [15]. In BPCS, a gray image consisting of n-bit pixels can be decomposed into n-binary planes. For example, n=8, as shown in Figure 1.Figure 1
Binary pixel blocks on bit-planes.For example,P is an n-bit gray image; here n=8. Therefore =P7P6P5P4P3P2P1P0, where P7 is the MSB bit-plane and P0 is the LSB bit-plane. Each bit-plane can be segmented into “informative” region and “noise-like” region. It is simple in informative region and cannot be used for hiding information. However, it is complex in noise-like region and each noise-like region could be replaced with another noise-like pattern in BPCS. As a result, it will not change the overall quality of image after embedding. The most important step in BPCS is how to locate noisy regions in a cover image correctly. The regular method is to divide each bit-plane of the cover image into small square binary pixel blocks. The blocks are considered as noisy regions; those have complex black-and-white patterns. Often α is defined as a criterion to judge whether the block is complex or not [16]:(1)α=k2×m×m-1,where k is the total length of border in a block, m is the row or column of the block, and α is between 0 and 1. If α is higher than the given threshold value, then the block is regarded as complex.


## 3. Improved BPCS Steganography

The black-and-white border complexity is a simple and easy method to judge whether the blocks are complex or not. However it is not always useful. For example, the blocks that have periodical patterns, such as chessboard or stripes, are recognized as complex ones in this way. That is because, as shown in Figure2, αa=1 and αb=1/2.Figure 2
Blocks with largeα while not complex.
(a)
Chessboard
(b)
StripesBut these blocks cannot be used for embedding data; otherwise the cover image will deteriorate obviously. There are two new techniques to differentiate complex blocks from simple ones in this paper: run-length irregularity and border noisiness.


### 3.1. Run-Length Irregularity

Run-length irregularity is the histogram which consists of the run-lengths of both black-and-white pixels in a row or in a column.Suppose thath[i] is the frequency of runs of i pixels either in black or in white and n is the length of the pixel sequence; then hs is used to measure the irregularity of a binary pixel sequence:(2)pi=h[i]∑j=1nh[j],hs=-∑i=1nhilog2pi.The value of hs is often normalized to [0,1] and denoted by h^s.If the size of block isn×n and ri and cj are the ith row andjth column of a block, then the run-length irregularity β of a block is defined as follows:(3)β=min⁡H^s(r)-,H^s(c)-,where(4)H^sr=h^sr0,…,h^srn-1,H^sc=h^sc0,…,h^scn-1.And X- is the mean of all the elements of X.According to the definition, the smaller row and column averages are taken as the value of the run-length irregularityβ. As seen in Figure 3, they are both periodic in row or column. As a result, every run-length irregularity β is 0, so they are simple and cannot be used for embedding.Figure 3
Blocks with largeβ but those are not complex.
(a)
β
=
0.745
(b)
β
=
0.694The run-length irregularityβ is only useful in row or column. If the block is regular in other directions, β will have nothing to do with it, as shown in Figure 3.


### 3.2. Border Noisiness

If data is embedded on the boundary of noisy regions and informative regions of cover image blocks, then the noisy regions will be expended. As a result, the cover image will be changed clearly.The border noisiness is based on the differences between adjacent binary pixel sequences in a block. Similarly if the block size isn×n and ri and cj are the ith row and jth column of a block, then the border noisiness γ of a block is defined as follows:(5)γ=1nmin⁡EfPxr,EfPxc,where(6)Pxr=ρr0⊕r1,…,ρrn-2⊕rn-1,Pxc=ρc0⊕c1,…,ρcn-2⊕cn-1.⊕ means bitwise exclusive OR, ρ(x) is the number of ones in a binary sequence x, and(7)EfX=1-VXmax⁡X⁡VX·X¯,where X={x0,…,xm-1}, V(X) = the variance of X, and X¯ = the average of X.The border noisinessγ is used to check if many black-and-white pixel borders are well distributed over a block along both the horizontal and the vertical directions.Though the blocks in Figures3(a) and 3(b) both have large run-length irregularity β  (βa=0.745,βb=0.694), their border noisiness γ is as little as 0.294 and 0.048, respectively. So they are not complex according to the border noisiness γ and are not suitable for embedding.


### 3.3. Default Threshold Values

In a word, a blockB is recognized as complex only if it satisfies the following conditions:(8)αB≥αt,βB≥βt,γB≥γt.Here, αt, βt, and γt are threshold values. Normally, the default threshold values are (9)αti=α¯-i·Δα0≤i≤506≤i≤7,βti=β¯-i·Δβ0≤i≤506≤i≤7,γti=γ¯-i·Δγ0≤i≤506≤i≤7.From the equation above, it can be concluded that the bit-plane is higher and the threshold value is larger. That is because it will raise noticeable changes for excessive embedding data in high bit-plane and will freely get enough embedding capacity in low bit-plane. There is a fact that these threshold values are default and not always optimal. They could be adjusted manually according to the actual conditions.


### 3.4. Canonical Gray Coding

Normally the pixel value of an image is represented by pure binary code (PBC). Canonical Gray coding (CGC) [17] is superior to pure binary code (PBC) in BPCS steganography, because PBC will encounter “Hamming cliff,” which means that a small change in pixel value will affect many bits of value [13]. CGC makes full use of characteristic of human vision system and works out this problem.Suppose thatbi and gi are the ith bit of the pure binary code and canonical Gray code with the same n-bit. The two codes are given by(10)b0b1⋯bn-1,g0g1⋯gn-1.The relationship between bi and gi is given:(11)gi=b0i=0bi-1⊕bii>0,bi=g0i=0bi-1⊕gi=g0⊕⋯⊕gii>0.Here ⊕ means exclusive OR operation.It consists of informative and noise-like regions in binary image. Informative regions are simple while noise-like regions are complex. If secret information is noise-like then it is embedded in noise-like regions of the cover image directly. However, if secret data is informative then it will be conjugated firstly so as to convert it into complex pattern.


### 3.5. Conjugation Operation of a Binary Image

Conjugation is used to convert simple blocks into complex ones. In order to extract original data embedded in the cover image, it should record which blocks of the original data are conjugated and which are not. This information is stored in a conjugation map. It should be embedded along with the resource file as blocks. Note that the blocks of the conjugation map should be also conjugated if they are not complex enough.IfP is a binary image with size of n×n and black pixel is its foreground while white pixel is its background. W and B, respectively, represent all-white and all-black patterns. Now two checkerboard patterns Wc and Bc are put forward. In particular, Wc has a white pixel at the upper-left position, and Bc is its complement. In binary image black-and-white pixels particularly mean a logical value of 1 and 0.NowP∗ is defined as the conjugate of P which satisfies(12)P∗=P⊕Wc.The most important property about conjugation is(13)αP∗=1-αP.This property could transform informative pattern to complex one, so both informative and noise-like regions could be used for embedding by conjugation operation.


### 3.6. Statistical Analysis

Though BPCS steganography algorithm is advantageous in imperceptibility, it would change the statistic characteristics of bit-plane block complexity. Because adjacent pixels in the high bit-planes have a strong correlation, the higher the bit-plane is, the stronger the correlation is. The method of steganalysis is proposed by Zhang and Wang [17]. Suppose the following. (1)  h0(c) is the complexity histogram of all the bit-plane blocks of cover image, and c is the complexity of a block, whose threshold value is θ·Cmax⁡. (2)  hI(c) is the complexity histogram of all the bit-plane blocks of secret image. If c is not as big as the threshold value θ·Cmax⁡, the blocks should be done by conjugation first. Finally hs(c) is the complexity histogram of all the bit-plane blocks of cover image in which secret data has been embedded, and is defined as follows:(14)hsc=h0(c)c≤θ·Cmax⁡hI(c)θ·Cmax⁡<c<(1-θ)·Cmax⁡hI(c)+hI(Cmax⁡-c)c≥1-θ·Cmax⁡.From (14), it can be concluded that hs(c) is composed of three parts of complexity histograms; each of them is smooth connection, but there is a sharp jump at the joint of two adjacent histograms, such as c=θ·Cmax⁡ and c=1-θ·Cmax⁡. The way of steganalysis is shown as follows:(15)dc=hc-1-hc+[h(Cmax⁡-c+1)-h(Cmax⁡-c)]aaaaaaaaaaaaaaaaaa0<c<0.5Cmax⁡.d(c) is defined to measure the discontinuity of the histogram. If there are obvious peak values which are larger than 0 in the d(c), then the cover image will be considered as embedding secret information.In order to resist BPCS statistical analysis, the basic principle of improved BPCS steganography algorithm adopted different bit-plane with different complexity, which the higher is, the complexity smaller is. The threshold value of bit-plane complexity is computed in the same way as in Section3.3 (see Table 2).


## 3.1. Run-Length Irregularity

Run-length irregularity is the histogram which consists of the run-lengths of both black-and-white pixels in a row or in a column.Suppose thath[i] is the frequency of runs of i pixels either in black or in white and n is the length of the pixel sequence; then hs is used to measure the irregularity of a binary pixel sequence:(2)pi=h[i]∑j=1nh[j],hs=-∑i=1nhilog2pi.The value of hs is often normalized to [0,1] and denoted by h^s.If the size of block isn×n and ri and cj are the ith row andjth column of a block, then the run-length irregularity β of a block is defined as follows:(3)β=min⁡H^s(r)-,H^s(c)-,where(4)H^sr=h^sr0,…,h^srn-1,H^sc=h^sc0,…,h^scn-1.And X- is the mean of all the elements of X.According to the definition, the smaller row and column averages are taken as the value of the run-length irregularityβ. As seen in Figure 3, they are both periodic in row or column. As a result, every run-length irregularity β is 0, so they are simple and cannot be used for embedding.Figure 3
Blocks with largeβ but those are not complex.
(a)
β
=
0.745
(b)
β
=
0.694The run-length irregularityβ is only useful in row or column. If the block is regular in other directions, β will have nothing to do with it, as shown in Figure 3.


## 3.2. Border Noisiness

If data is embedded on the boundary of noisy regions and informative regions of cover image blocks, then the noisy regions will be expended. As a result, the cover image will be changed clearly.The border noisiness is based on the differences between adjacent binary pixel sequences in a block. Similarly if the block size isn×n and ri and cj are the ith row and jth column of a block, then the border noisiness γ of a block is defined as follows:(5)γ=1nmin⁡EfPxr,EfPxc,where(6)Pxr=ρr0⊕r1,…,ρrn-2⊕rn-1,Pxc=ρc0⊕c1,…,ρcn-2⊕cn-1.⊕ means bitwise exclusive OR, ρ(x) is the number of ones in a binary sequence x, and(7)EfX=1-VXmax⁡X⁡VX·X¯,where X={x0,…,xm-1}, V(X) = the variance of X, and X¯ = the average of X.The border noisinessγ is used to check if many black-and-white pixel borders are well distributed over a block along both the horizontal and the vertical directions.Though the blocks in Figures3(a) and 3(b) both have large run-length irregularity β  (βa=0.745,βb=0.694), their border noisiness γ is as little as 0.294 and 0.048, respectively. So they are not complex according to the border noisiness γ and are not suitable for embedding.


## 3.3. Default Threshold Values

In a word, a blockB is recognized as complex only if it satisfies the following conditions:(8)αB≥αt,βB≥βt,γB≥γt.Here, αt, βt, and γt are threshold values. Normally, the default threshold values are (9)αti=α¯-i·Δα0≤i≤506≤i≤7,βti=β¯-i·Δβ0≤i≤506≤i≤7,γti=γ¯-i·Δγ0≤i≤506≤i≤7.From the equation above, it can be concluded that the bit-plane is higher and the threshold value is larger. That is because it will raise noticeable changes for excessive embedding data in high bit-plane and will freely get enough embedding capacity in low bit-plane. There is a fact that these threshold values are default and not always optimal. They could be adjusted manually according to the actual conditions.


## 3.4. Canonical Gray Coding

Normally the pixel value of an image is represented by pure binary code (PBC). Canonical Gray coding (CGC) [17] is superior to pure binary code (PBC) in BPCS steganography, because PBC will encounter “Hamming cliff,” which means that a small change in pixel value will affect many bits of value [13]. CGC makes full use of characteristic of human vision system and works out this problem.Suppose thatbi and gi are the ith bit of the pure binary code and canonical Gray code with the same n-bit. The two codes are given by(10)b0b1⋯bn-1,g0g1⋯gn-1.The relationship between bi and gi is given:(11)gi=b0i=0bi-1⊕bii>0,bi=g0i=0bi-1⊕gi=g0⊕⋯⊕gii>0.Here ⊕ means exclusive OR operation.It consists of informative and noise-like regions in binary image. Informative regions are simple while noise-like regions are complex. If secret information is noise-like then it is embedded in noise-like regions of the cover image directly. However, if secret data is informative then it will be conjugated firstly so as to convert it into complex pattern.


## 3.5. Conjugation Operation of a Binary Image

Conjugation is used to convert simple blocks into complex ones. In order to extract original data embedded in the cover image, it should record which blocks of the original data are conjugated and which are not. This information is stored in a conjugation map. It should be embedded along with the resource file as blocks. Note that the blocks of the conjugation map should be also conjugated if they are not complex enough.IfP is a binary image with size of n×n and black pixel is its foreground while white pixel is its background. W and B, respectively, represent all-white and all-black patterns. Now two checkerboard patterns Wc and Bc are put forward. In particular, Wc has a white pixel at the upper-left position, and Bc is its complement. In binary image black-and-white pixels particularly mean a logical value of 1 and 0.NowP∗ is defined as the conjugate of P which satisfies(12)P∗=P⊕Wc.The most important property about conjugation is(13)αP∗=1-αP.This property could transform informative pattern to complex one, so both informative and noise-like regions could be used for embedding by conjugation operation.


## 3.6. Statistical Analysis

Though BPCS steganography algorithm is advantageous in imperceptibility, it would change the statistic characteristics of bit-plane block complexity. Because adjacent pixels in the high bit-planes have a strong correlation, the higher the bit-plane is, the stronger the correlation is. The method of steganalysis is proposed by Zhang and Wang [17]. Suppose the following. (1)  h0(c) is the complexity histogram of all the bit-plane blocks of cover image, and c is the complexity of a block, whose threshold value is θ·Cmax⁡. (2)  hI(c) is the complexity histogram of all the bit-plane blocks of secret image. If c is not as big as the threshold value θ·Cmax⁡, the blocks should be done by conjugation first. Finally hs(c) is the complexity histogram of all the bit-plane blocks of cover image in which secret data has been embedded, and is defined as follows:(14)hsc=h0(c)c≤θ·Cmax⁡hI(c)θ·Cmax⁡<c<(1-θ)·Cmax⁡hI(c)+hI(Cmax⁡-c)c≥1-θ·Cmax⁡.From (14), it can be concluded that hs(c) is composed of three parts of complexity histograms; each of them is smooth connection, but there is a sharp jump at the joint of two adjacent histograms, such as c=θ·Cmax⁡ and c=1-θ·Cmax⁡. The way of steganalysis is shown as follows:(15)dc=hc-1-hc+[h(Cmax⁡-c+1)-h(Cmax⁡-c)]aaaaaaaaaaaaaaaaaa0<c<0.5Cmax⁡.d(c) is defined to measure the discontinuity of the histogram. If there are obvious peak values which are larger than 0 in the d(c), then the cover image will be considered as embedding secret information.In order to resist BPCS statistical analysis, the basic principle of improved BPCS steganography algorithm adopted different bit-plane with different complexity, which the higher is, the complexity smaller is. The threshold value of bit-plane complexity is computed in the same way as in Section3.3 (see Table 2).


## 4. Improved BPCS Steganography Algorithm

(1)
Convert the cover image and the secret image from pure binary code (PBC) into canonical Gray code (CGC).
(2)
Calculate complexity measuresα, β, and γ for each block of each bit-plane of cover image and secret image.
(3)
Perform conjugation operation on the “simple” or “informative” blocks of the secret image.
(4)
In order to contradict statistical steganalysis, the threshold valueθ is calculated.
(5)
Perform embedding operation to embed secret image in cover image.
(6)
Convert the embedded image from CGC to PBC.


## 5. Experiment

In this paper, the experiment is done with MATLAB 7. The block size is8×8, and the peak signal-to-noise ratio (PSNR) and capacity are used to evaluate the quality of the cover image after embedding:(16)PSNR=20log102551/N∑i=0N-1Ii′-Ii2.Ii is the value of a pixel in the original image and Ii′ is the value of the same pixel after embedding, respectively. N is the number of pixels.Capacity means the number of bits that could be used for embedding.This paper adopts three different images as samples. The size of image is512×512.From Table1, it can be shown that though capacity is almost the same between BPCS and the proposed method, the PSNR value is much different. It also can be concluded that the proposed approach is better in PSNR value and capacity than existing techniques.Table 1
Comparison of PSNR value and capacity with different methods.
Image
Lena
Baboon
Jet
Capacity/bit
BPCS (α=0.4)
951783
984782
942457
Proposed method
954140
982769
943296
Mandal and Das [10]
145787
144916
145648
Juneja and Sandhu [8]
561345
830546
505658
LSB
467004
720785
463758
PSNR/db
BPCS (α=0.4)
42.86
40.85
41.37
Proposed method
45.71
42.76
44.39
Mandal and Das [10]
42.26
38.44
42.60
Juneja and Sandhu [8]
44.59
36.36
42.50
LSB
41.01
33.99
39.38Table 2
Threshold valuesβ, γ, and θ of each bit-plane.
i
0
1
2
3
4
5
6
7
β
t
0.632
0.583
0.534
0.485
0.436
0.387
0
0
γ
t
0.394
0.351
0.308
0.265
0.222
0.179
0
0
θ
i
0.562
0.448
0.334
0.220
0.106
0
0
0As shown in Figure4, h0, h1, and h2 are the histograms of original image, BPCS, and improved BPCS.Figure 4
Two kinds of differences histograms.The PSNR of the image obtained by BPCS (Figure5(b)) and improved BPCS (Figure 5(c)) was 45.71 dB and 42.86 dB. Figures 5(d), 5(e), and 5(f) show the part areas of the images in Figures 5(a), 5(b) and 5(c) respectively. It can be found that there is deterioration in the image obtained by BPCS (Figure 5(e)) but not in the image obtained by improved BPCS (Figure 5(f)). The experiment also shows that improved BPCS can not only embed more data but also keep the image quality higher. In a word, improved BPCS is superior to BPCS in steganography.Figure 5
Comparison of BPCS and improved BPCS.
(a)
(b)
(c)
(d)
(e)
(f)


## 6. Conclusion

It is shown that the final embedded image with the proposed method seems to be the same as the original image and locates noise-like regions in a cover image more exactly. It also shows that the algorithm in this paper can withstand statistics analysis while the way of BPCS cannot. Experiments also prove that the proposed approach is better in PSNR value and capacity than existing techniques.In this paper, some parameters and thresholds are got by experiment. How to determine these values automatically needs to be researched in the future.



---

*Source: 698492-2015-03-26.xml*