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 block-wise 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 gray-level 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 real-time 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 gray-level image. In the encoding stage, I is first partitioned
into a set of non-overlapping kxk blocks and the mean value pm 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 ph and pl are computed for each block, i.e., the mean values of those pixels with p(x, y)>pm and p(x, y) = pm respectively. Thus, each block is represented by a pair of integers ph, pl 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 ph, pl 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, pm, ph and pl are rounded to their nearest integers.
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 = (u1,u2,
uK) and v = (v1,v2,
vK-1). The main idea of our model is to encrypt u and meanwhile v is also hidden in two shares m=(m1,m2,
mK) and n=(n1,n2,
nK). The encryption strategy of this model is shown in Fig. 1.
The encoding procedures are described below:
Step 1: Encrypt u1 in m1 and n1. Randomly select a 1 or 0 and assign it to m1 and then n1 is determined by m1 and u1 as:
Step 2: Hide v1 in n1 and m2. That is, n1 and v1 as determine m2:
Step 3: Encrypt u2 in m2 and n2. That is, m2 and u2 as determine n2:
Step 4: Repeat the above operations until vj-1 is hidden in nj-1 and mj as indicated with the dash arrow and uj is encrypted in mj and nj 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 exclusive-OR 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.
strategy of the joint data encryption and data hiding model
In the encoding stage, operations are given below:
1: Perform the standard BTC encoding on the first block and its pm,
ph and pl are obtained
2: Compute the difference d between pm and pl
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.
3: Translate pl and d into 8-bit and 7-bit binary sequences,
respectively. Concatenate them to form a 15-bit sequence denoted by v=(v1,
, v15). Besides, rearrange the bitmap M
into a 16-bit binary sequence, represented with u=(u1, u2,
4: Apply the encoding procedure (Eq. 4-6)
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
, m16) and n = (n1,
5: For the first share, translate (m1, m2,
m8) and (m9, m10,
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.
6: Repeat the above operations for all the other blocks and the share
images S1 and S2 are obtained and transmitted independently.
The corresponding operations in the decoding stage are described as follows:
1: Translate the received first two pixels of S1 and S2
into two 16-bit binary sequences, respectively.
2: Apply the decoding procedure (Eq. 7-8)
of the joint data encryption and data hiding model to these two sequences.
Thus pl, d and the associated bitmap M are recovered. Suppose
the number of 0s and 1s in M are nl
and nh=16-nl, respectively.
3: Compute pm according to pl and d as:
4: Compute ph according to pl and pm
5: Reconstruct the BTC-compressed block based on pl, pm
and M according to Eq. 3.
6: Repeat Steps 1-5 for all the other received shares pixels
and thus the BTC-compressed image is reconstructed.
The 512x512 gray-level 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.
results on Lena image, (a) the original image, (b) the constructed image
by our scheme, (c) the share image S1, (d) the share image
results on the received shares suffering transmission errors, (a) the
corrupted S1, (b) the corrupted S2 (c) the reconstructed
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 block-wise 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
ph for image reconstruction in our scheme is not exactly equal to
that directly transmitted in the standard BTC. Namely, error is introduced in
Eq. 9-11 when a floating-point 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 7-bit 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 gray-level 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 256-bin histogram of d values is shown in Fig. 4. The bins at the high end (bins from 150-255) 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, pm= ps, pl = ps,
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.
histogram of values
Thus we set ph= ps and remain all the other operations
Actually, our scheme is also suitable for BTC-compressed color image transmission. Specifically, the original color image is decomposed into red, green and blue channels and each channel is encoded as a gray-level image. Finally all encoded channels are recomposed into color noise-like shares.
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 random-noise like share images. If r or more than
r shares are collected, the original image can be reconstructed. Thien and Lins
scheme is an alternative method to encrypt the BTC-compressed 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 ph, pl and
M of a block) from the range (0, 255) to (0, 250) before encryption. In other
words, to perfectly reconstruct the BTC-compressed 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).
A joint secret sharing and data hiding system is proposed for BTC-compressed 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.
This study is financially supported by National Scientific Fund of China, under the granted No. of 61003255.