An Efficient Information Hiding Scheme Based on Closest Paired Tree Structure Vector Quantization

Zhi-Hui Wang,Chin-Chen Chang,and Ting-Yu Lin

1.Introduction

Information hiding in digital images is important for the transfer of secret information that malicious attackers cannot recognize in data communication[1].Due to requirements for reducing the cost of Internet bandwidth and speeding up the transmission time,digital images are usually compressed to reduce the storage size prior to transmission.As a result,information hiding is done in the compression domain of digital images,which means that the compression code of an image is altered to hide secret information.This has become an interesting topic receiving increased attention[2]-[4].

Among all lossy or lossless compression mechanisms,vector quantization(VQ)is a classical data compression technique that has been widely used in many applications because of its simplicity and efficiency[5].In a VQ system,an image is divided into several non-overlapping n×n sized blocks.Each block finds the most similar n×n dimensional codeword from the VQ codebook and puts the index of the codeword into the index table to replace the original image block.An image is encoded into an index table after VQ compression.In 2005,Yang et al.[6]proposed a fast correlation-based information hiding technique to hide information into the compression results of the VQ compressed image.In 2007,Chang et al.[7]proposed a new scheme based on the declustering of VQ compressed codes,which achieves a significant improvement in hiding capacity.In 2009,Chang et al.[8]proposed another novel locally adaptive coding based information hiding method for VQ indices to further improve the performance of the previous works.

However,there is a limitation to VQ that the compression ratio of VQ depends on the dimensions of the codeword.Side match vector quantization(SMVQ)was proposed to improve the performance of VQ[9].SMVQ utilizes the fact that the edges of the neighboring blocks look similar to predicting a state codebook.Some researchers have developed information hiding schemes based on SMVQ[10]-[13]because it has better compression performance than VQ.Shie et al.proposed an adaptive data hiding scheme based on SMVQ,which is capable of hiding considerable quantities of secret data while preserving an acceptable visual quality for cover image[12].In order to improve the hiding capacity and visual image quality,Lee et al.proposed another scheme based on SMVQ that exploits image block characteristics[13].The secret data are embedded into edge blocks and non-sufficiently smooth blocks to avoid the large distortion of smooth blocks in Lee et al.’s scheme.

In order to save processing time for both VQ and SMVQ,especially the time for the encoding procedure,a tree structure vector quantization(TSVQ)compression technique was proposed in [14].TSVQ uses a tree structure to accelerate the encoding time of VQ.In this paper,we propose a novel information hiding scheme based on closest paired tree structure vector quantization(CPTSVQ),which is an improved version of TSVQ.By using the time efficiency of CPTSVQ,the proposed scheme achieves better efficiency for information hiding.

The rest of this paper is organized as follows.Section 2 introduces the CPTSVQ compression procedure.The details of the proposed scheme is described in Section 3.Section 4 presents the experimental results.Finally,conclusions are given in Section 5.

2.Closest Paired Tree Structure Vector Quantization

In this section,we briefly describe CPTSVQ.Generally,CPTSVQ is an adaptive method based on TSVQ,which uses an empty root full binary tree,called a Compare-tree,to perform the compression operation.An example of a Compare-tree is shown in Fig.1.The codebook of CPTSVQ is composed by the leaves of the Compare-tree,and the size of the codebook is the amount of leaves in the Compare-tree.In Section 2.1,we introduce the Compare-tree building.In Section 2.2,we describe the compression procedure.

2.1 Compare-Tree building

The following is a detailed encoding procedure for how to build the Compare-tree of CPTSVQ.

Step 1.Divide the images used for building the Compare-tree into non-overlapping blocks with size n×n pixels.

Step 2.Each block is treated as a vector,which has n×n dimensions.Collect all vectors to compose the group Code(0).

Step 3.Calculate every dimension’s mean value for all vectors in Code(0).All calculated mean values form a gravity center node(0).By comparing the Euclidean distance between a vector in Code(0)and the origin point(0,0,··,0)with the Euclidean distance between the origin point(0,0,···,0)and the node(0),we can divide all vectors in Code(0)into two groups,named Code(1)and Code(2).

Step 4.Find the gravity center node(1)of Code(1)and the gravity center node(2)of Code(2).Build a new binary tree,called Compare-tree with an empty node as the root.Add node(1)and node(2)on the first level of the Compare-tree.

Step 5.Following this rule,calculate the gravity center node(i)of Code(i)and divide Code(i)into two groups Code(2i+1)and Code(2i+2).Add the gravity centers node(2i+1)and node(2i+2)of the new generated groups Code(2i+1)and Code(2i+2)on the level(+1)of the Compare-tree until the number of leaves equals the size of the codebook that we are trying to build.

Step 6.Each leaf node leafiin the Compare-tree is the ith codeword in the codebook.

Step 7.Compute the Euclidean distance between every two codewords in the codebook.Find the closest codeword for each codeword in the codebook.Set the ith codeword’s closest codeword as cpi,which can be used to enhance the image quality during the compression.The Compare-tree is first presented in Fig.1,and then shown with the newly calculated indices of the closest codewords Fig.2.

2.2 Compression Procedure

After constructing the codebook and calculating the closest codewords,this information is used for the image compression.The following steps detail the compression procedure for an image.

Fig.1.Compare-tree with eight codewords.

Fig.2.Compare-tree with the indices of the closest codewords.

Step 1.Divide the image into non-overlapping blocks,with size n×n pixels.

Step 2.Select an unprocessed block V of the image as the root of the Compare-tree.

Step 3.Compute the Euclidean distance disLbetween V and its left child node in the Compare-tree.Also compute the Euclidean distance disRbetween V and its right child node in the Compare-tree.

Step 4.Compare the values of the disLand the disR.If disLis smaller than disR,traverse the left child node.Otherwise,traverse the right child node.

Step 5.Repeat Step 3 and Step 4 until the leaf node leafiof the Compare-tree has been found.

Step 6.Compute the Euclidean distance disleafbetween V and leafi.Calculate the Euclidean distance discpbetween V and leafi’s closest codeword cpi.Compare the distance values between the disleafand discp,use the codeword index of the smallest one as the compression index.

Step 7.Repeat Step 2 through Step 6 until all blocks of the image have been processed.

Afterward,an image can be encoded into an index table by CPTSVQ.

3.Proposed Scheme

The proposed information hiding scheme based on CPTSVQ is described in this section.Assume that the data to be embedded into the cover image are binary stream S.Rather than finding one closest codeword for each codeword of a codebook in CPTSVQ,the proposed scheme finds the two closest codewords for each ith codeword in the codebook.The Compare-tree with the two closest codewords for each leaf node is shown in Fig.3.

Fig.3.Compare-tree with two indices of two closest codewords for every leaf node.

Fig.4.Test images:(a)Lena,(b)Jet,(c)Pepper,(d)Baboon,and(e)Barbara.

Table 1:PSNR and execution time for TSVQ,CPTSVQ,and the proposed scheme using a codebook with 512 code words,with 4×4 block size

Table 2:PSNR and execute time for TSVQ,CPTSVQ,and the proposed scheme using a codebook with 512 code words,with 2×2 block size

The details of the encoding process with information hiding of the proposed scheme are described as follows.

Step 1.Divide the cover image into non-overlapping blocks with size n×n pixels.

Step 2.Select an unprocessed block V of the image as the root of the Compare-tree.

Step 3.Compute the Euclidean distance disLbetween V and its left child node in the Compare-tree.Also compute the Euclidean distance disRbetween V and its right child node in the Compare-tree.

Step 4.Compare the values of the disLand the disR.If disLis smaller than disR,traverse the left child node.Otherwise,traverse the right child node.

Step 5.Repeat Steps 3 and 4 until finding the leaf node leafi.Let leafjbe the sibling node of leafi.

Step 6.Let cpi1and cpi2be the closest codewords of leafi,and cpj1and cpj2be the closest codewords of leafj,respectively.

Step 7.Delete the duplicate indices to generate the candidate index set.

Step 8.Let s be the embedded secret bit.If s is 0,select the closest index,whose index value is even.Otherwise,select the closest index,whose index value is odd.

Step 9.Repeat Step 2 through Step 8 until all blocks of the image have been processed.

Finally,we can generate the embedded VQ index table.In the information extraction procedure,the receiver can obtain the embedded secret stream S by extracting the least significant bit(LSB)of each index in the index table.In addition,the cover image can be lossy recovered by reconstructing every block with the codeword found in the codebook using the index of the block.

4.Experimental results

In this section,some experimental results are presented to demonstrate the high efficiency of the proposed scheme.The experiments were conducted on an Intel Core i5 CPU and implemented with MATLAB R2010a.In the experiments,we utilized five grayscale images sized 512×512,as shown in Fig.4,as the test images.

Table 1 and Table 2 present the comparison results of the execution time and visual quality of the decoded image between TSVQ,CPTSVQ,and the proposed scheme when the sizes of the blocks are 4×4 and 2×2,respectively.

The image quality was evaluated using a peak signal-to-noise ratio(PSNR)defined as

H and W are the height and width of the image,and Xi,jandare the cover image’s pixel value and stego image’s pixel value,respectively.It can be observed that neither the execution time nor the visual quality of the proposed scheme degraded much compared with the performances of TSVQ and CPTSVQ.

The hiding capacity(HC)can be calculated with(2),where the size of the block is n×n and that of the cover image is H×W.

For example,assume that the size of cover image and the size of the block are 512×512 and 4×4,respectively.The hiding capacity is 16384 bits.If the block size reduces to 2×2,the hiding capacity will increase to 65536 bits.That is,the block size greatly affects the hiding capacity.

To illustrate the performance of our scheme,we compare two representational SMVQ-based information hiding methods,Shie et al.’s scheme[12],and Lee et al.’s scheme[13]with the proposed scheme.

Table 3 shows a comparison of the results for execution time and decoded image quality among Shie et al.’s scheme[12],Lee et al.’s scheme[13],and the proposed scheme when embedding 64K-bits of secret information.Here,the execution time is the processing time of the encoding procedure without counting the processing time of building the codebook.

Two kinds of codebooks,smooth codebook and complex codebook,are used in Shie et al.’s method.The variance of pixels in a block is used to determine whether the block is smooth or complex.Shie et al.’s method[12]uses the smooth block of a cover image to hide information.Lee et al.’s method[13]uses a smooth codebook and four kinds of edge blocks:horizontal(EW)codebook,vertical(NS)codebook,+45°degree(NW)codebook,and -45°degree(ES)codebook.The edge type of the pixel block is obtained by multiplying the four kinds of edge masks shown in Fig.5.

Table 3:Comparison of results for Shie et al.’s scheme[12],Lee et al.’s scheme[13],and the proposed scheme when hiding 64 Kb of secret information

Fig.5.Four edge masks(from left to right,up to down:EW,NS,NW,and ES).

Our proposed scheme spends less than half the amount of time to finish the operation of transforming the cover image into the index table with the secret data embedded in it.This proves that our method has higher efficiency than Shie et al.’s scheme[12]and Lee et al.’s scheme[13].

In addition,the PSNR value in Shie et al.’s scheme[12]and Lee et al.’s scheme[13]highly depends on the codebooks to achieve satisfactory results.The decoded image quality of the proposed scheme is better than the other two methods when embedding the same quantity of the secret data.

5.Conclusions

In this article,we propose a novel image information hiding scheme based on CPTSVQ.The proposed scheme can reduce the computation complexity.The execution time is less than half that of related works.Moreover,we can achieve satisfactory quality of the de-compressed VQ image.

[1]C.-S.Chan and C.-C.Chang,“A survey of information hiding schemes for digital images,” Int.Journal of Computer Sciences and Engineering Systems,vol.1,no.3,pp.187–200,Jul.2007.

[2]X.Zhang,S.Wang,Z.Qian,and G.Feng,“Reversible fragile watermarking for locating tampered blocks in JPEG images,” Signal Processing,vol.90,no.12,pp.3026–3036,Dec.2010.

[3]C.-Y.Lin,C.-C.Chang,and Y.-C.Wang,“Reversible steganographic method with high payload for JPEG images,” IEICE Trans.on Information and Systems,vol.E91-D,no.3,pp.836–845,Mar.2008.

[4]Z.Qian and X.Zhang,“Lossless data hiding in JPEG bitstream,” Journal of Systems and Software,vol.85,no.2,pp.309–313,Feb.2012.

[5]R.M.Gray,“Vector quantization,” IEEE ASSP Magazine,vol.1,no.2 ,pp.4–29,Apr.1984.

[6]B.Yang,Z.-M.Lu,and S.-H.Sun,“Reversible watermarking in the VQ compressed domain,” in Proc.of the Fifth IASTED Int.Conf.on Visualization,Benidorm,Spain,2005,pp.298–303.

[7]C.-C.Chang,Y.-P.Hsieh,and C.-Y.Lin,“Lossless data embedding with high embedding capacity based on declustering for vq-compressed codes,” IEEE Trans.on Information Forensics and Security,vol.2,no.3,pp.341–349,Sep.2007.

[8]C.-C.Chang,T.-D.Kieu,and Y.-C.Chou,“Reversible information hiding for VQ indices based on locally adaptive coding,” Journal of Visual Communication and Image Representation,vol.20,no.1,pp.57–64,Jan.2009.

[9]R.-F.Chang and W.-T.Chen,“Side-match vector quantization for reconstruction of lost blocks,” Journal of Visual Communication and Image Representation,vol.4,no.2,pp.171–177,Jun.1993.

[10]C.-C.Chang and W.-C.Wu,“A steganographic method for hiding secret data using side match vector quantization,”IEICE Trans.on Information and Systems,vol.E88-D,no.9,pp.2159–2167,Sep.2005.

[11]C.-C.Chang and T.-C.Lu,“Reversible index-domain information hiding scheme based on side-match vector quantization,” Journal of Systems and Software,vol.79,no.8,pp.1120–1129,Aug.2006.

[12]S.-C.Shie,S.-F.Lin,and C.-M.Fang,“Adaptive data hiding based on SMVQ prediction,” IEICE Trans.on Information and Systems,vol.E89-D,no.1,pp.358–362,Jan.2006.

[13]C.-F.Lee,H.-L.Chen,and S.-H.Lai,“An adaptive data hiding scheme with high embedding capacity and visual image quality based on SMVQ prediction through classification codebooks,” Image and Vision Computing,vol.28,no.8,pp.1293–1302,Aug.2010.

[14]A.Lowry,“Binary search trees for vector quantization,” in Proc.of Int.Conf.on Acoustics,Speech,and Signal Processing,Dallas,1987,pp.2205–2208.