INTRODUCTION
In recent years, the security of data storage and transmission has drawn much
attention among researchers (Ruan et al., 2010).
Block Truncation Coding (BTC) (Amarunnishad et al.,
2008; Guo et al., 2009) is a popular lousy
image compression method due to low computational complexity and storage demands.
It never requires any auxiliary information during the encoding and decoding
procedures. However, transmission security is also a problem must be considered
in more and more situations. Besides traditional data encryption algorithms
(e.g., DES), secret sharing (Ahlswede and Csiszar, 1993;
Luo et al., 2010; Zhao
et al., 2010) and data hiding (Pan et al.,
2007) are another two powerful complementary techniques and also play important
roles in information security.
The block truncation coding compression is based on a blockwise thresholding operation. Hence, the task of block truncation coding compressed image transmission is reduced to transmitting binary matrices and thresholds of image blocks. The compression ratio is determined by the partitioned block size. That is, a larger block size partition results to fewer binary matrices and thresholds to be transmitted. However, the compressed image quality is worse than that obtained by a smaller block size partition. Consequently, a good tradeoff is usually achieved between the compression ratio and the reconstructed image quality.
In this study, we aim to develop a secure transmission system for block truncation coding compressed images. The application scenario can be described as follows. Given a graylevel or color image, we need to compress and transmit it over two independent but not secure channels. Besides transmission security, the following three factors must be considered in the system design. (1) The reconstruction image quality should be preserved, i.e., nearly the same as that in block truncation coding compression. (2) Low complexity encoding and decoding, thus the realtime performance of block truncation coding compression is maintained. (3) Small size of shares. This is essential to save transmission time and channel resources. In fact, in most available secret sharing methods, the sizes of shares are expanded compared to the original secret data.
In particular, these three advantages are achieved in the proposed system with secret sharing and data hiding well synthesized. The compressed image can be reconstructed as long as both shares are collected. Otherwise, no meaningful information is decrypted. Besides, the encoding/decoding procedures are quite simple and the reconstructed image quality is nearly the same as that in block truncation coding compression. Furthermore, each share is half size of the compressed image and thus no extra burden is laid on transmission channels.
The standard BTC compression technique is reviewed below. Suppose the original
image I is a graylevel image. In the encoding stage, I is first partitioned
into a set of nonoverlapping kxk blocks and the mean value p_{m} of
each block is calculated as:
where, p(x, y) denotes the pixel value in the position (x, y). Next, the block pixels are thresholded as:
resulting in a binary bitmap M, where b(x, y) is the pixel value in the position (x, y) of M. Third, two quantization levels p_{h} and p_{l} are computed for each block, i.e., the mean values of those pixels with p(x, y)>p_{m} and p(x, y) = p_{m} respectively. Thus, each block is represented by a pair of integers p_{h}, p_{l} in the range of (0, 255) and a kxk bitmap. The encoding procedure is completed and the compressed content is transmitted.
In the decoding stage, each block can be approximately recovered with p_{h}, p_{l} and M as:
where, p'(x, y) is the reconstructed pixel value in the position (x, y) of the current decoded block. In this way, the decoded image can be reconstructed by collecting all the reconstructed blocks. In our context, p_{m}, p_{h} and p_{l} are rounded to their nearest integers.
PROPOSED SCHEME
Our scheme is conducted as a part of the project work on satellite image transmission from Feb, 2009. The design and test duration is completed till Sep., 2010.
Joint data encryption and data hiding model: We start from presenting the joint data encryption and data hiding model. Suppose the secret data is composed by two binary sequences u = (u_{1},u_{2},…u_{K}) and v = (v_{1},v_{2},…v_{K1}). The main idea of our model is to encrypt u and meanwhile v is also hidden in two shares m=(m_{1},m_{2},…m_{K}) and n=(n_{1},n_{2},…n_{K}). The encryption strategy of this model is shown in Fig. 1.
The encoding procedures are described below:
Step 1: Encrypt u_{1} in m_{1} and n_{1}. Randomly select a “1” or “0” and assign it to m_{1} and then n_{1} is determined by m_{1} and u_{1} as:
Step 2: Hide v_{1} in n_{1} and m_{2}. That is, n_{1} and v_{1} as determine m_{2}:
Step 3: Encrypt u_{2} in m_{2} and n_{2}. That is, m_{2} and u_{2} as determine n_{2}:
Step 4: Repeat the above operations until v_{j1} is hidden in n_{j1} and m_{j} as indicated with the dash arrow and u_{j} is encrypted in m_{j} and n_{j} as indicated with the solid arrow.
In this way, the sequence u is encrypted and v is hidden in two produced shares m and n.
In decoding, the sequences u and v can be recovered as:
where denotes the exclusiveOR operation.
Joint block truncation coding and secret sharing: In the joint BTC and secret sharing scheme, the standard BTC compression and the joint data encryption and data hiding model are applied. In our case, the original image is partitioned into 4x4 blocks.

Fig. 1:  Encryption
strategy of the joint data encryption and data hiding model 
In the encoding stage, operations are given below:
•  Step
1: Perform the standard BTC encoding on the first block and its p_{m},
p_{h} and p_{l} are obtained 
•  Step
2: Compute the difference d between p_{m} and p_{l}
as: 
Considering in natural images, pixel values change gradually in a 4x4 block, the difference d is small for most natural image blocks. Therefore, it is reasonable to regard d as an integer belongs to (0, 127), otherwise we set d = 127.
•  Step
3: Translate p_{l} and d into 8bit and 7bit binary sequences,
respectively. Concatenate them to form a 15bit sequence denoted by v=(v_{1},
v_{2},…, v_{15}). Besides, rearrange the bitmap M
into a 16bit binary sequence, represented with u=(u_{1}, u_{2},…,
u_{16}). 
•  Step
4: Apply the encoding procedure (Eq. 46)
of the joint data encryption and data hiding model to the block. Thus
u is encrypted and at the same time v is hidden in two produced shares
m=(m_{1}, m_{2},…, m_{16}) and n = (n_{1},
n_{2},…, n_{16}). 
•  Step
5: For the first share, translate (m_{1}, m_{2},…,
m_{8}) and (m_{9}, m_{10},…, m_{16})
into two integers in the range of (0, 255), respectively. The similar
operations are also performed on n for the second share. In this way,
the compressed information of each block corresponds to two shares, each
with two “pixels”. 
•  Step
6: Repeat the above operations for all the other blocks and the share
images S_{1} and S_{2} are obtained and transmitted independently. 
The corresponding operations in the decoding stage are described as follows:
•  Step
1: Translate the received first two pixels of S_{1} and S_{2}
into two 16bit binary sequences, respectively. 
•  Step
2: Apply the decoding procedure (Eq. 78)
of the joint data encryption and data hiding model to these two sequences.
Thus p_{l}, d and the associated bitmap M are recovered. Suppose
the number of “0”s and “1”s in M are n_{l}
and n_{h}=16n_{l}, respectively. 
•  Step
3: Compute p_{m} according to p_{l} and d as: 
•  Step
4: Compute p_{h} according to p_{l} and p_{m}
as: 
•  Step
5: Reconstruct the BTCcompressed block based on p_{l}, p_{m}
and M according to Eq. 3. 
•  Step
6: Repeat Steps 15 for all the other received shares’ pixels
and thus the BTCcompressed image is reconstructed. 
EXPERIMENTAL RESULTS
The 512x512 graylevel Lena image is selected as the test image and the related
experimental results are shown in Fig. 2. Obviously, the two
128x256 share images produced in our scheme look like random noises, thus transmission
security of the compressed image can be guaranteed.

Fig. 2:  Experimental
results on Lena image, (a) the original image, (b) the constructed image
by our scheme, (c) the share image S_{1}, (d) the share image
S_{2} 

Fig. 3:  Experimental
results on the received shares suffering transmission errors, (a) the
corrupted S_{1}, (b) the corrupted S_{2} (c) the reconstructed
image 
Furthermore, the total amount of the transmission content is the same as that
in the standard BTC compression, i.e., the compression ratio is kept as 4.Many
transmission scenarios, especially wireless transmissions usually suffer some
abrupt errors such as packet loss (Lee et al., 2007).
As our scheme is based on a blockwise processing mechanism, these transmission
errors of share images only corrupt the associated decrypted blocks. In other
words, errors are not diffused to other reconstructed blocks, as illustrated
in another experiment shown in Fig. 3. Figure
3a and b are the corrupted versions of Fig.
2c and d respectively. From Fig. 3c,
it is easy to find that only the corresponding blocks are corrupted, while others
still reconstructed correctly.
It is necessary to note that, compared with the reconstructed image based on
the standard block truncation coding; there is a slight quality degradation
of the reconstructed image with the two intact shares. This is due to the computed
p_{h} for image reconstruction in our scheme is not exactly equal to
that directly transmitted in the standard BTC. Namely, error is introduced in
Eq. 911 when a floatingpoint number is
rounded to its nearest integer. A large quantity of experimental results shows
that this image quality degradation is acceptable. For example, the PSNR of
the reconstructed Lena using the standard BTC is 34.00 dB, while 33.96 dB obtained
in our scheme.
As mentioned earlier d is set as 127 when it is larger than 127 such that it can be translated into 7bit sequence. Thus truncation errors may be produced for the range of d is (0, 255) theoretically. Fortunately, as high correlation exists among pixels in natural image blocks, d is small in most cases. Ten 512x512 graylevel images (Lena, Baboon, Barbara, Bridge, Boat, F16, Peppers, Elaine, Aerial, Truck) are selected to investigate the statistics of d values. Each image is partitioned into 4x4 blocks, thus totally 163840 blocks, i.e., 163840 d values are obtained and examined. The 256bin histogram of d values is shown in Fig. 4. The bins at the high end (bins from 150255) are empty and hence only a part (150 out of 256) of the histogram is shown. In this experiment, only 44 d values are larger than 127. In addition, these large d values are in the range of (128, 150). That is, the percentage of the special case is merely about 0.027% and thus the possible errors are acceptable in practical.
In addition, there is another special case in our scheme, i.e., all the pixels
in an original image block are of the same value. Suppose this value is denoted
by ps. In this case, p_{m}= p_{s}, p_{l} = p_{s},
d = 0 and all bits in the bitmap M are 0. Obviously, Eq. 11
cannot be applied any longer for both its denominator and numerator equal 0.

Fig. 4:  Statistical
histogram of values 
Thus we set p_{h}= p_{s} and remain all the other operations
unchanged.
Actually, our scheme is also suitable for BTCcompressed color image transmission. Specifically, the original color image is decomposed into red, green and blue channels and each channel is encoded as a graylevel image. Finally all encoded channels are recomposed into color noiselike shares.
DISCUSSION
In Thien and Lin (2002), Thien and Lin develop a Lagrange
interpolation based (r, t)threshold scheme for image secret sharing. An input
image can be encrypted into t randomnoise like share images. If r or more than
r shares are collected, the original image can be reconstructed. Thien and Lin’s
scheme is an alternative method to encrypt the BTCcompressed image with r =
t =2. For example, a 512x512 input image can be encrypted into two 128x256 shares.
However, this is achieved by truncating all compressed “pixel” values
(e.g., 4 “pixels” translated from p_{h}, p_{l} and
M of a block) from the range (0, 255) to (0, 250) before encryption. In other
words, to perfectly reconstruct the BTCcompressed image, the truncation errors
must be also encrypted additionally. Consequently, two produced shares are usually
larger than 128x256 pixels, resulting in more storage space and transmission
time. The same mechanism is also adopted in the subsequent work (Chen
and Lin, 2005).
As a possible solution, the truncation errors also can be hidden along with
the secret data. This can be referred to the side information hiding strategy
proposed in several data hiding algorithms (Fridrich et
al., 2002; Pan et al., 2007; Guo
et al., 2009) and secret sharing techniques (Luo
et al., 2010; Zhao et al., 2010).
CONCLUSIONS
A joint secret sharing and data hiding system is proposed for BTCcompressed image secure transmission. The compressed content is encrypted and hidden in two share images. Since each share image is half size of the compressed content, the available channel resources are enough for share image transmission. Not only the standard BTC compression properties such as low encoding/decoding complexity and acceptable reconstructed image quality are still preserved, but also transmission security is guaranteed because each block is encrypted individually.
ACKNOWLEDGMENTS
This study is financially supported by National Scientific Fund of China, under the granted No. of 61003255.