Advanced
Reversible Data Hiding Scheme for VQ Indices Based on Absolute Difference Trees
Reversible Data Hiding Scheme for VQ Indices Based on Absolute Difference Trees
KSII Transactions on Internet and Information Systems (TIIS). 2014. Jul, 8(7): 2572-2589
Copyright © 2014, Korean Society For Internet Information
  • Received : February 12, 2014
  • Accepted : May 17, 2014
  • Published : July 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Chin-Chen Chang
Department of Biomedical Imaging and Radiological Science, China Medical University Taichung 40402, Taiwan, R.O.C
Thai-Son Nguyen
Department of Information Technology, Tra Vinh University Tra Vinh Province, Vietnam
Chia-Chen Lin
Department of Computer Science and Information Management, Providence University, Taichung 43301, Taiwan, R.O.C

Abstract
Reversible data hiding is a technique for recovering original images without any distortion after secret data are extracted from the image. The technique continues to attract attention from many researchers. In this paper, we introduce a new reversible data hiding scheme based on the adjacent index differences of vector quantization (VQ) indices. The proposed scheme exploits the differences between two adjacent indices to embed secret data. Experimental results show that our scheme can achieve a lower compression rate than an earlier scheme by Yang and Lin. Our scheme’s average compression rate, 0.44 bpp, outperforms that of Yang and Lin’s scheme, which averages 0.53 bpp. Moreover, the embedding capacity of our scheme can rise to 1.45 bpi, which also is superior to that of Chang et al.’s scheme [35] (1.00 bpi)Yang and Lin’s scheme [27] (0.91 bpi) as well as Chang et al.’s scheme [26] (0.74 bpi).
Keywords
1. Introduction
W ith the rapid progress in multimedia and Internet technologies, most digital data can be transmitted over the Internet without time or space constraints. However, the Internet’s open environment means that transmitted data may be exposed to illegal or unauthorized modification or may be eavesdropped upon. Therefore, protecting transmitted data from such attacks has become a critical issue. Over the past ten years, lots of research results have been dedicated to find solutions that enhance the security of transmitted data. Generally, data protection techniques can be divided into two approaches: cryptography and data hiding. Cryptography transforms secret data into a meaningless form by using cryptographic algorithms such as DES [1] or AES [2] . The meaningless form gives the transmitted data some protection, but it also may raise the suspicions of attackers. By contrast, data hiding hides secret data in meaningful cover media, such as images, videos, audios or texts, before it is transmitted over the Internet. The original nature of the cover media remains even through it carries the secret data. Therefore, it is more difficult for malicious attackers to distinguish whether a media object carries secret data. In other words, the security of the hidden data is guaranteed.
There are two basic types of data hiding schemes. The first is irreversible data hiding, which embeds secret data into a cover image to generate a stego-image. The use of irreversible data hiding maintains the security of secret data when it is transmitted over the Internet. Many irreversible data hiding schemes [3 - 13] have been proposed. The merit of irreversible data hiding is that its hiding capacity is quite high. Take for example least significant bit (LSB) substitution [13] , one of the most popular irreversible data hiding schemes. With LSB substitution, the number of hidden secret bits of each pixel in a cover image can range from 1 bit to 4 bits. However, the one weakness in irreversible data hiding is that it does not allow a cover image to be recovered exactly after secret data are extracted.
The second type of data hiding is reversible data hiding, also called lossless data hiding. Reversible data hiding compensates for the weakness in irreversible data hiding with its reversibility feature. This reversibility enables the cover image to be reconstructed exactly after secret data are extracted. Many reversible data hiding schemes [14 - 22] have been proposed in the past five years. In 2002, Fridich et al. [16] introduced a reversible data hiding scheme that compresses the least significant bits (LSBs) of pixels in the cover image, appends the secret data to be compressed, and encrypts the data and, finally, replaces the LSB of the cover image with the encrypted codes. However, Fridich et al.’s scheme does not offer a high embedding capacity. Also in 2002, Celik et al. [15] proposed a new reversible data hiding scheme that improved on Fridich et al.’s scheme by using vector quantization and lossless compression. Celik et al.’s scheme offers lower distortion of the stego-image and higher hiding capacity than those of Fridich et al.’s scheme. In 2003, Tian [21] proposed a reversible data hiding scheme that relies on the difference expansion between a pair of pixels. With Tian’s scheme, one secret bit can be embedded by depending on the expansion difference between a pair of pixels. To improve the hiding capacity of Tian’s scheme, in 2004 Alattar [14] presented a new reversible data hiding scheme that uses a vector in place of the pixel pair in Tian’s scheme. Alattar’s scheme successfully embeds more bits into each vector; therefore, it not only achieves computational efficiency but also increases hiding capacity.
Typically, cover images used in data hiding schemes can be divided into three domains: the spatial domain, the transform domain and the compression domain. In spatial domain schemes [5 , 6 , 9 - 16] , secret data are embedded by modifying the cover image’s spatial information. In the transform domain [8 , 23 - 25] , secret data are embedded by shifting the coefficient values of the cover image. However, these two techniques require larger bandwidth and storage space to transmit stego-media because the stego-media become larger than the cover media after secret data are embedded. Therefore, spatial and transform domain schemes are not suitable when transmission bandwidth is limited. Compression domain schemes are considered the best choice in this case because the compression codes are significantly smaller than the cover image before data hiding. Even with the hidden data, the compression code size is still smaller than the cover image. Research over the past five years has relied on compression codes generated by VQ-based or SMVQ-based compression [26 - 28 , 29 , 30 , 31 , 34 , 35] , BTC [32] and DCT [33] , to carry secret data simply because of this characteristic.
In these compression domain schemes, many scholars have tried to embed secret data into VQ-compressed images [26 - 28 , 30 , 31] . In 2006, Lin and Chang [31] introduced a data hiding scheme that relies on a pair of dissimilar codewords in the sorting codebook to embed one secret bit. In 2007, Chang et al. [26] proposed a reversible data hiding scheme by clustering the VQ codebook into three groups. Only the VQ indices located in group with the highest referred counts are used to hide one secret bit of data. The other two groups are used for the future recovery of image data. In 2009, Chen and Huang [28] proposed a hybrid scheme that combines the dynamic tree coding scheme (DTCS) and modified search order coding (MSOC) to encode the index table completely and efficiently without any extra coding distortion. By depending on the useful information in the left and upper blocks adjacent to the current processing block, they applied the HLIC method to embed secret information. To improve the embedding capacity and compression rate of Chang et al.’s scheme [26] , Yang and Lin [27] proposed new VQ-based reversible data hiding scheme. In this scheme, Yang and Lin sort and divide the VQ codebook into 2 B clusters, where B is the number of secret bits embedded into each VQ index, and half of the clusters are used to embed secret data. However, the average compression rate and average embedding rate of Yang and Lin’s scheme are still around 0.5 bpp and 0.9 bpi, respectively. In 2013, Chang et al. [35] proposed a new compression and information hiding hybrid scheme based on SMVQ and search order coding (SOC). Their scheme obtained both the low compression rate and the high embedding capacity when compare with Chang et al.’s scheme [26] and Yang and Lin [27] . However, the embedding rate obtained by their scheme is small because most of the indices simply embed one bit of secret data. To further improve the embedding rate while achieving a better compression rate, in this paper, we introduce a new reversible data hiding scheme based on the differences between neighboring index values in the index table. Experimental results confirm that our proposed scheme offers better compression and embedding rates than the schemes proposed by Chang et al. [26 , 35] and Yang and Lin [27] , while maintaining the same visual image quality as those three schemes.
The rest of this paper is organized as follows. Section 2 reviews VQ and Yang and Lin’s scheme. Details of the proposed scheme are described in Section 3. Experimental results are discussed in Section 4. Finally, some conclusions are given in Section 5.
2. Related Work
In this section, we first introduce traditional vector quantization (VQ) because our proposed scheme embeds secret data into VQ-generated indices. Then, Yang and Lin’s VQ-based reversible data hiding scheme is introduced.
- 2.1 Vector quantization
In 1984, Gray [3] proposed vector quantization, also called VQ. The VQ technique is well-known for both its lossy data compression and its efficient clustering. The main idea behind VQ is that the k -dimensional space Rk is mapped into its finite subset Y ={ y i ; i =1,2, … , N }, where y i is called a codeword and the set Y is called a codebook.
In VQ, a codebook must be generated by a set of training images and clustering algorithm in advance. The well-known iterative generalized Lloyd algorithm also called Linde-Buzo-Gray algorithm (LBG) [3] is often used to generate codebooks for VQ. As Fig. 1 shows, in VQ, an image is first decomposed into several non-overlapping blocks, with each block treated as a vector and all blocks encoded sequentially in raster scan order. In the encoding phase, each k -dimensional input vector x =( x 1 , x 2 , …, xk ) is compared with the codewords in the codebook to determine the nearest codeword, which is based on the Euclidian distance defined in Equation (1).
PPT Slide
Lager Image
Encoding flowchart of the VQ encoder
Here, the similarity between the input vector x and a codeword y i of the codebook is measured by the Euclidian distance shown in Equation (1):
PPT Slide
Lager Image
where xj is the j th component of the input vector x , and y ij is the j th component of the codeword y i . Once a codeword with the nearest Euclidian distance is found, it is used to encode the current processing input vector. An index table is generated after all vectors are processed, and the index table is sent to the receiver.
In the decoding phase, the same codebook is used to find the corresponding codeword for each index of the received index table. Then the original image can be recovered. The index table is the result of VQ encoding. Because the index table is smaller than the original image, the objective of VQ compression is achieved. Assume an original image size 512×512 is divided into a vector with 16 dimensions, and a codebook is sized 256. Each vector requires only 8 bits after VQ compression; therefore, the VQ compression rate is 1/2 (bpp). However, by using the Euclidian distance formula in Equation (1), the index values of the nearest codewords are found during compression processing. Some distortion between the original image and the reconstructed image may occur. Thus, VQ is a lossy compression scheme.
- 2.2 Yang and Lin’s reversible data hiding scheme
In 2009, Yang and Lin [27] proposed a new reversible data hiding scheme based on VQ. The purpose of Yang and Lin’s scheme is to improve the embedding capacity of Chang et al.’s scheme [26] . Assume that codebook Y = ( y 0 , y 1 ,…, y n−1 ) with size n is given. Y’ is the sorted codebook with a size n' =
PPT Slide
Lager Image
× 2 B that is created and divided into 2 B groups, where B is the number of secret bits embedded into each VQ index. All groups are the same size as m =
PPT Slide
Lager Image
. In this scheme, half of the indices in Y’ are used to embed secret data and at least 2 B-1 indices are used as indicators. For an image I , each block Ii is encoded into index y i by VQ coding. yi is then transformed into yi , where yi is the corresponding index in a group and sometimes includes an indicator. To better explain Yang and Lin’s scheme, the function tranj ( yi ) is used to represent the transformation function, where yi is transformed into the corresponding index in group Cj . Fig. 2 shows an example of Yang and Lin’s scheme when B is 1. In Yang and Lin’s scheme, if index yi belongs to group C0 , yi' is set to trans0 ( yi ) when secret bit s =0 is hidden and yi' is set to trans1 ( yi ) when secret bit s =1 is hidden. If the index y i belongs to group C1 , indicator I0 is added ahead by setting yi' to I0 trans1 ( yi ), and no secret data is hidden.
PPT Slide
Lager Image
Example of Yang and Lin’s scheme with B=1
In the embedding phase, the grayscale image I sized W × H is used to embed secret data and the secret message is denoted as S = ( s 0 , s 1 ,…, sr ), where sj = {0,1} and 0 ≤ j r . The following algorithm shows the embedding phase in detail.
Embedding algorithm
Input: Cover image I , secret message B , codebook Y' divided into 2 groups, C0 , and C1 .
Output: Transformed index table IT' .
Step 1: Encode cover image I by using the VQ encoder to produce index table IT .
Step 2: Read index y from index table IT and read secret bit s from the secret message S .
Step 3: If y C0 , and s =0, y is unchanged by setting y' = trans0(y) .
Step 4: If y C0 , and s =1, transfer y to group C1 by setting y' = trans1(y) .
Step 5: If y C1 , no secret data is hidden, and y is transferred by setting y' = I0 trans1(y) , where I0 is the indicator.
Step 6: Repeat Steps 2 to 5 until all indices in the index table are processed.
After the entire index table IT is transferred into the transformed index table IT' , the sender sends IT' and codebook Y' with its two groups, C0 , and C1 , to the receiver. When the receiver gets this information from the sender side, the receiver performs the following steps to obtain secret message S and recover the original index table IT .
Extracting algorithm
Input: Transformed index table IT' and codebook Y' , which is divided into two groups, C0 , and C1 .
Output: Recovered index table IT and secret message S .
Step 1: Read index y' from the index table IT' .
Step 2: If y' has no indicator, original index y is recovered by using the formula y = trans0 (y') and 1-bit secret data s is extracted according to the following rules. If y' Ck , then s = k (i.e., if y' C1 , s =1. Otherwise, if y' C0 , s =0).
Step 3: If y' has indicator I0 and y' = I0 y" recover y by using the formula y = trans1 (y") , and no secret data is extracted in this case.
Step 4: Repeat Steps 1 to 3 until index table IT' is processed completely.
After the extracting phase is completed, secret message S is extracted and the original index table IT is reconstructed exactly. Then the traditional VQ decoder can be applied to reconstruct cover image I .
3. Proposed Scheme
To achieve the high compression and embedding rate performance of Yang and Lin’s scheme [27] while maintaining the same image quality in the reconstructed image, this section presents a novel reversible data hiding scheme based on the difference between adjacent indices in the index table. The proposed scheme encodes the VQ index table into a binary code stream and hides secret data during the encoding process. Comparing with some previous data hiding schemes [26 , 27 , 35] in the VQ domain, the proposed scheme achieves both a higher embedding capacity and a higher compression rate.
For this discussion, the cover image is grayscale image I sized W × H , with codebook Y = ( y 0 , y 1 ,… y n-1 ) , and the secret message is denoted as S = (s0,s1,…,sr) , where sj = {0,1} and 0 jr . Our proposed reversible data hiding scheme can be divided into two phases: data embedding phase and data extracting phase. These two phases are discussed in Subsections 3.1 and 3.2, respectively.
- 3.1 Data embedding phase
Fig. 3 is a flowchart of our data embedding phase, which involves three operations: determining the scan path and computing adjacent indices’ differences, constructing the absolute difference tree and data embedding.
PPT Slide
Lager Image
Flowchart of data embedding algorithm
The determining the scan path and computing adjacent indices’ differences phase is first operation. To obtain all the directional adjacent indices’ differences in the index table of the cover image, nine scan paths must be used in this phase. To better explain this step, the basic scan paths are shown in detail in the 4 × 4 indices in Fig. 4 . After applying one of the scan paths in Fig. 4 , the sequence of index values is obtained as v 1 , v 2 ,…, vk , where k is the size of the index table.
PPT Slide
Lager Image
Nine basic scan paths
After the sequence of index values v 1 , v 2 ,…, vk is obtained according to the determined scan path, a sequence of adjacent index differences, D = { d 1 , d 2 ,…, dk }, is calculated by using Equation (2). Adjacent index difference di can be a negative or positive value.
PPT Slide
Lager Image
Four steps must be performed to construct the absolute difference tree in the second operation. In an absolute difference tree, each node represents the absolute difference value of two neighboring indices based on the determined scan path. The absolute difference tree can be divided into four levels. As Fig. 5 shows, the root is level 0 and the four child nodes of the root make up level 1. For level 2, 12 nodes (i.e., node 0 to node 11) which are the child nodes of the level 2 are generated. In the same way, level 3 consists of the child nodes of level 2, which are labeled node 0 to node 31. Note that each absolute difference value larger than 31 also belongs to level 3. For each level, a different bit number is used to encode the members in the different level. For example, 4 bits is used for level 0, 7 bits for level 1, 9 bits for level 2 and 11 bits for level 3, respectively. Note that 7 bits contains a 2-bit indicator, 1 bit a sign of the difference value and a 4-bit binary representation of the corresponding child value, as described in Step 5.2 of the data embedding algorithm. Clearly, the absolute difference value belongs to the smaller level; thus, fewer bits are required for encoding. In this case, if a larger level is created (i.e., level 4), the compression rate will be less. Therefore, the proposed scheme uses only four levels.
PPT Slide
Lager Image
Example of the absolute difference tree
Step 1: The value 0 is first chosen as the root node of the absolute difference tree.
Step 2: The four child nodes of the root are added and their order is set as 0, 1, 2, and 3.
Step 3: Choose 4 child nodes for each of nodes 1, 2 and 3. Note that the order of the child nodes starts with 0, and the 12 nodes generated for level 2 are labeled node 0 to node 11.
Step 4: Keep choosing a new child for each node that has value between 4 and 11. Again, the order of new child nodes starts with 0, and the 32 nodes generated for level 3 are labeled node 0 to node 31. Construction of the absolute difference tree stops when Step 4 is completed.
As Fig. 5 shows, once the four steps are completed the absolute difference tree is created. The purpose of constructing an absolute difference tree is to provide important information for the embedding process. In Fig. 5 , some gray nodes do not have child nodes because the gray nodes have already used in a lower level. For example, the white node 0 in level 0 already has four child nodes; therefore, the gray node 0 in level 1 does not have child nodes. The nodes of the absolute difference tree are classified into two cases. If the absolute difference value d belongs to the elements of level 0, level 1, or level 2 (absolute difference value ranges from 0 to 11), it is classified in Case 1 and two secret bits are embedded. Otherwise, the absolute difference value d belongs to Case 2 and no secret bit can be embedded.)
Our proposed data embedding phase can be broken into six steps. The corresponding algorithm is presented in detail here.
Data embedding algorithm
Input: Grayscale cover image I , codebook Y , secret message S .
Output: Code stream CS in binary form.
Step 1: Encode cover image I by using a VQ encoder to obtain index table IT .
Step 2: Determine a scan path. Next, compute adjacent indices’ differences to generate the sequence of adjacent indices’ differences D . Then, construct the absolute difference tree using the four steps described earlier. Finally, depending on the absolute difference tree, encode each index difference value of the sequence of adjacent index differences D .
Step 3: Read index difference value d from the sequence of adjacent indices’ differences D .
Step 4: If 11<| d |, this case belongs to Case 2 of the absolute difference tree, and no secret bit is hidden. Therefore, d is encoded by r =00║ sign ( d )║(| d |) 2 , and r is concatenated into code stream CS , where sign ( d ) is defined in Equation (3), (| d |) 2 is the 8-bit binary representation of the absolute value of d , and “║” represents the concatenation operation.
PPT Slide
Lager Image
Step 5: Otherwise (i.e., | d |≤11), this is Case 1 of the absolute difference tree, the embedding case. The next two secret bits s 1 s2 are read from the secret message B .
Step 5.1: If d = 0, encode d by r =01║ s 1 s2 and concatenate r into code stream CS .
Step 5.2: If 1 ≤| d |≤ 3, encode d by r =10║ sign ( d )║ w2 , where sign(d) is defined in Equation (3). w is the child node of d in the absolute difference tree in Fig. 5 , w is calculated as in Equation (4), and w2 is the 4-bit binary representation of w . Finally, concatenate r into code stream CS .
PPT Slide
Lager Image
Step 5.3: If 4 ≤| d |≤ 11, encode d by r =11║ sign ( d )║ q2 , where sign ( d ) is defined in Equation (3), q is the child node of d in the absolute difference tree in Fig. 5 , q is calculated by Equation (5), and q2 is the 6-bit binary representation of q . Finally, concatenate r into code stream CS .
PPT Slide
Lager Image
Step 6: Repeat Steps 2 to 5 until all difference values in D are processed.
After all steps are completed, code stream CS is obtained. Finally, the sender sends the code stream CS and the determined scan path to the receiver. To better explain our data embedding phase, an example is shown in Fig. 6 . Assume VQ encoding is conducted and one index table sized 4×4 is generated as shown in Fig. 6 . A scan path as shown in Fig. 3 (a) is determined.
PPT Slide
Lager Image
Example of the embedding phase of our scheme with a 4×4 index table and the scan path of Fig. 3(a).
Along the Fig. 3 (a) scan path, the adjacent indices’ differences are generated by using Equation (2). Assume secret message S is “100011011011” and the absolute difference tree is generated as in Fig. 5 . The first difference value is “1”, so | d |=1≤11. This is Case 1 of the absolute difference tree, the embedding case. According to Step 5.2, the 2-bit indicator should be “10”, and the two secret bits s1s2 =10 are read from secret message S . Finally, d is encoded by r =10║0║0010, and r is concatenated into code stream CS . The second difference index value is 13, so | d |=13 ≥12. This case belongs to Case 2 of the Fig. 5 . Therefore, no secret data is embedded. Finally, r = 00║0║00001101 and is concatenated into code stream CS according to Step 4. For the fourth difference index value, d =0, and two secret bits s1s2 =11 are encoded by r =01║11. Then r is concatenated into code stream CS . Depending on the data embedding algorithm described earlier, the entire sequence of adjacent index differences will be encoded and code stream CS will be obtained.
- 3.2 Data extracting phase
When the receiver gets code stream CS from the sender, the receiver extracts secret message S and reconstructs original index table IT by performing the following steps to recover original image I . A detailed flowchart of our proposed extracting phase is presented in Fig. 7 .
PPT Slide
Lager Image
Flowchart of our extracting phase
Data extracting algorithm
Input: Code stream CS .
Output: Secret message S and the original index table IT .
Step 1: Read 2 bits p from code stream CS .
Step 2: If p =00, no secret data is hidden. The original difference index value d is reconstructed according to the following operations. First, read 1 following bit as the sign of d by using Equation (3). Next, read the 8 next bits and convert them into decimal values as | d |. Finally, d is sent to the sequence of adjacent indices’ differences D .
Step 3: If p =01, read the two next bits as two secret bits s1s2 . The original difference index d is recovered as 0. Then concatenate s1s2 into secret message S and insert d into the sequence of adjacent indices’ differences D.
Step 4: If p =10, then reconstruct d by using following processes. First, read 1 next bit as the sign of d . Then, read the 4 next bits and change them to decimals as w , then calculate | d | by using Equation (6).
PPT Slide
Lager Image
Two secret bits s1s2 is extracted by using Equation (7).
PPT Slide
Lager Image
Then, send d to sequence D and concatenated s1s2 into secret message S .
Step 5: If p =11, then reconstruct d by using following processes. Read 1 next bit as the sign of d . Read 6 next bits and change them to decimals as w . Then compute | d | by using Equation (8).
PPT Slide
Lager Image
After that, extract 2 secret bits s1s2 by using Equation (9).
PPT Slide
Lager Image
Then, the original difference index value d is sent to the sequence of adjacent indices’ differences D , and s1s2 is concatenated into secret message S .
Step 6: Repeat Steps 1 to 5 until the entire code stream CS is processed.
Step 7: Recover the original index table by reversing the adjacent index difference process depending on the scan path used.
After the extracting phase is completed, the original index table is reconstructed and secret message S is extracted. Then, original image I can be regenerated from the reconstructed index table by using the VQ decoder.
4. Experimental Classification Results and Analysis
This section describes the experiments conducted to demonstrate the performance of our proposed scheme in hiding capacity, compression rate and visual quality of the recovered image. Three existing schemes, Chang et al.’s schemes [26 , 35] and Yang and Lin’s scheme [27] , were compared with ours. In our experiments, the size of each non-overlapping image block was 4×4, with each block a 16-dimensional vector. The codebook used in our experiments was sized 256 and was trained by using the well-known LBG algorithm [3] with three training grayscale images, “Lena”, “F16” and “Boat”. The six general grayscale test images shown in Fig. 8 , “Lena”, “Boat”, “Peppers”, “F16”, “Tiffany”, and “Baboon”, were used in our experiments. All computing was performed on a PC with a 2.1GHz Intel(R) Core™2 CPU and a 1-GB RAM. The operating system was Windows 7 Professional and our algorithm was programmed by Microsoft Visual Studio 2005 C#.
PPT Slide
Lager Image
Six 512×512 grayscale test images
We evaluated the performance of our scheme against three criteria: hiding capacity, compression rate and visual quality of the recovered image. The evaluation criteria are described in the following paragraphs. The compression rate ( CR ) is the ratio of the size of the compression output code stream to the size of the original cover image and is defined in Equation (10).
PPT Slide
Lager Image
where ║ I' ║ is the size of the output code stream, and H and W are the height and width of the cover image. Bit per pixel (bpp) is the CR unit. The use of CR allows us to estimate compression performance. Basically, the smaller the compression rate the better the compression performance. In contrast, the larger the compression rate the poorer the compression performance. Fig. 9 compares the results for our scheme, Chang et al.’s scheme and Yang and Lin’s scheme in compression rate.
PPT Slide
Lager Image
Comparison of compression rate for our proposed scheme using scan path 7 in Fig. 3(g), and for Chang et al.’s schemes and Yang and Lin’s scheme
In addition, to evaluate the hiding performance of our proposed scheme the embedding rate ( ER ) is defined as in Equation (11). ER shows how many secret bits can be embedded into each index of the cover image.
PPT Slide
Lager Image
where ║ S ║ is the number of bits that can be embedded into a cover image and NIDX is the number of indices in the index table generated by VQ compression. The higher the embedding rate is, the larger the secret message can be embedded. The embedding performance results for our scheme and the two existing schemes used for comparison are shown in Fig. 10 .
PPT Slide
Lager Image
Embedding rate results of our proposed scheme with scan path 7 of Fig. 3(g) compared with the two existing schemes
The third measure is visual quality of the recovered image because visual quality is used to estimate the degree of distortion between the original cover image and the recovered image. Peak signal-to-noise ( PSNR ) ratio is used to evaluate image quality, as shown in Equation (12).
PPT Slide
Lager Image
where the mean square error ( MSE ) for a W × H grayscale image is defined as in Equation (13).
PPT Slide
Lager Image
where Iij and Iij are the pixel values of the cover and stego-images, respectively. However, our scheme, Chang et al.’s schemes and Yang and Lin’s scheme are all VQ-based reversible data hiding schemes. Therefore, the visual quality for all four schemes is exactly the same.
Because our proposed scheme has nine scan paths, three test images, “Baboon”, “Tiffany” and “F16”, were selected to show the possible embedding rate and the compression rate with the nine scan paths, as shown in Table 1 .
Comparisons of different scan paths in ER and CR with our scheme
PPT Slide
Lager Image
Comparisons of different scan paths in ER and CR with our scheme
Table 1 makes it clear that scan path 7 is the best path in our scheme because it achieves an average compression rate of 0.46 bpp and an average embedding rate of 1.4 bpi. Moreover, scan path 7 also works well with complex images. As for smooth images, there are three scan paths, paths 1, 5 and 7 that can achieve the same average compression rate (0.37 bpp) and average embedding rate (1.86 bpi). Therefore, scan path 7 is used with our scheme to compare with three existing schemes in the rest experiments.
Fig. 9 shows the compression performance of our proposed scheme, Chang et al.’s schemes [26 , 35] and Yang and Lin’s scheme [27] . Clearly, our scheme outperforms the other two schemes in compression rate. The average compression rate of our scheme is 0.44 bpp. By contrast, the average compression rate of Chang et al.’s scheme [35] , Yang and Lin’s scheme [27] , and Chang et al.’s scheme [26] is only 0.48bpp, 0.53 bpp, and 0.55 bpp, respectively. Our proposed scheme’s superior compression rate results from encoding the difference value of two adjacent indices instead of the original index value. In most cases, each adjacent index value generated by our proposed computing adjacent indices’ values phase can be encoded by using fewer bits. For example, if the absolute difference value of two adjacent indices d is “0”, the difference value is encoded by indicator 01, with two secret bits concatenated. Only 4 bits are required for this case. In contrast, if the absolute value of the adjacent index difference value equals 20, our scheme must use 11 bits to encode the current adjacent index difference (i.e., 00║0║00010100). Luckily, a large absolute value of the adjacent index difference occurs infrequently. It only occurs when the content of an image has significant variation. Therefore, our scheme offers a better compression rate for smooth images than for complex images. Take the test images “Baboon” and “Tiffany”, for example. With our scheme the compression rate for “Baboon” is larger than that for “Tiffany” because “Tiffany” is smoother than “Baboon”. Note that for the complex image “Baboon”, the compression rate with our scheme remains 0.56 bpp, which is still lower than the rates achieved by Yang and Lin’s scheme [27] (0.57 bpp), Chang et al.’s scheme [35] (0.63 bpp), or Chang et al.’s scheme [26] (0.64 bpp).
Fig. 10 compares embedding performance for our scheme, Chang et al.’s schemes [26 , 35] and Yang and Lin’s scheme [27] . Clearly, our scheme’s embedding rate is significantly higher than the others. The average embedding rate of our scheme is approximately 1.45 bpi, followed by Chang et al.’s scheme [35] (1.00 bpi) and Yang and Lin’s scheme [27] (0.91 bpi). The worst embedding rate is Chang et al.’s scheme [26] (0.74 bpi). Our scheme’s embedding rate is superior because two bits can be embedded in most adjacent index differences.
5. Conclusion
This paper proposes a novel reversible data hiding based on adjacent indices’ differences. The average compression rate of our proposed scheme is 0.44 bpp, which is superior to Yang and Lin’s scheme (0.53 bpp) or Chang et al.’s scheme (0.54 bpp). Moreover, our scheme’s compression rate is also better than that offered by traditional VQ compression schemes (i.e., 0.5 bpp for a codebook sized 256). In addition, the average embedding rate of our scheme can be as much as 1.45 bpi, which outperforms Chang et al.’s scheme [35] (1.00 bpi), Yang and Lin’s scheme [27] (0.91 bpi), and Chang et al.’s scheme [26] (0.74 bpi). Finally, the visual quality of our scheme is as good as Yang and Lin’s and Chang et al.’s schemes ( PSNR >30dB). Therefore, the overall superior performance offered by our scheme enables us to conclude that it is efficient and flexible enough to be applied directly in some applications such as digital libraries or online multimedia transmission.
BIO
Chin-Chen Chang received the B.S. degree in applied mathematics and the M.S. degree in computer and decision sciences from National Tsing Hua University, Hsinchu, Taiwan, R.O.C., in 1977 and 1979, respectively. He received the Ph.D degree in computer engineering from National Chiao Tung University, Hsinchu, in 1982. From July 1998 to June 2000, he was Director of the Advisory Office, Ministry of Education, R.O.C. From 2002 to 2005, he was a Chair Professor at National Chung Cheng University. From February 2005, he has been a Chair Professor at Feng Chia Univeristy. In addition, he was severed as a consultant to several research institutes and government departments. His current research interests include database design, computer cryptography, image compression, and data structures.
Thai-Son Nguyen received the bachelor degree in information technology from Open University, HCM city, Vietnam, in 2005. From December 2006, he has been lecturer of TraVinh University, TraVinh, Vietnam. In 2011, he received M.S. degree in computer sciences from FengChia University, TaiChung, Taiwan. He is currently pursuing the Ph.D. degree with the Department of Information Engineering and Computer Science, Feng Chia University, Taichung, Taiwan. His current research interests include data hiding, image processing, database security and information security.
Chia-Chen Lin (M’08) received the B. S. degree in information management from the Tamkang University, Taipeo, Taiwan, R.O.C., in 1992. She received the M.S. degree in information management and the Ph.D. degree in information management from Chiao Tung University, Hsinchu, Taiwan, in 1994 and 1998, respectively. She was a Visiting Associate Professor at Business School, University Illinois at Urbana Champain, during August 2006 to July 2007. She is currently a Professor in the Department of Computer and Information Management, Providence University, Sha-Lu, Taiwan. Her research interests include image and signal processing, image data hiding, mobile agent, and electronic commerce.
References
Davis R. M. 1978 “The data encryption standard in perspective” IEEE Commun. Mag. Article (CrossRef Link) 16 (6) 5 - 9    DOI : 10.1109/MCOM.1978.1089771
Rivest R. , Shamir A. , Adleman L. 1978 “A method for obtaining digital signature and public key cryptosystems” Commun. ACM Article (CrossRef Link) 21 (2) 120 - 126    DOI : 10.1145/359340.359342
Gray R. M. 1984 “Vector quantization” IEEE ASSP Mag. Article (CrossRef Link) 1 (2) 4 - 29    DOI : 10.1109/MASSP.1984.1162229
Bender W. , Morimoto N. , Lu A. 1996 “Technique for data hiding” IBM Systems Journal Article (CrossRef Link) 35 313 - 336    DOI : 10.1147/sj.353.0313
Chan C. K. , Cheng L. M. 2004 “Hiding data in images by simple LSB substitution” Pattern Recognition Article (CrossRef Link) 37 469 - 474    DOI : 10.1016/j.patcog.2003.08.007
Chan C. K. , Cheng L. M. 2001 “Improved hiding data in images by optimal moderately significant-bit replacement” IEEE Electronic Letters Article (CrossRef Link) 37 1017 - 1018    DOI : 10.1049/el:20010714
Chung K. L. , Shen C. H. , Chang L. C. 2001 “A novel SVD and VQ-based image hiding scheme” Pattern Recognition Article (CrossRef Link) 2 1051 - 1058    DOI : 10.1016/S0167-8655(01)00044-7
Marvel L. M. , Boncelet C. G. , Retter C. T. 1999 “Spread spectrum image steganography” IEEE Transactions on Image Processing Article (CrossRef Link) 8 1075 - 1083    DOI : 10.1109/83.777088
Mielikanen J. 2006 “LSB matching revisited” IEEE Signal Processing Letter Article (CrossRef Link) 13 285 - 297    DOI : 10.1109/LSP.2006.870357
Thien C. C. , Lin J. C. 2003 “A simple and high hiding capacity method for hiding digit-by-digit data in images based on modulus function” Pattern Recognition Article (CrossRef Link) 36 2875 - 2881    DOI : 10.1016/S0031-3203(03)00221-8
Wang R. Z. , Lin C.F. , Lin J. C. 2000 “Hiding data in images by optimal moderately significant-bit replacement” IEEE Electronic Letters Article (CrossRef Link) 36 2069 - 2070    DOI : 10.1049/el:20001429
Wang R. Z. , Lin C.F. , Lin J. C. 2001 “Image hiding by optimal LSB substitution and generic algorithm” Pattern Recognition Article (CrossRef Link) 34 671 - 683    DOI : 10.1016/S0031-3203(00)00015-7
Zhang X. , Wang S. 2005 “Steganography using multiple-base notational system and human vision sensitivity” IEEE Signal Processing Letters Article (CrossRef Link) 12 67 - 70    DOI : 10.1109/LSP.2004.838214
Alattar A. M. 2004 “Reversible watermarking using the difference expansion of a generalized integer transform” IEEE Transactions on Image Processing Article (CrossRef Link) 13 1147 - 1156    DOI : 10.1109/TIP.2004.828418
Celik M. U. , Sharma G. , Tekalp A.M. , Saber E. 2002 “Reversible data hiding” in Proc. of IEEE Int. Conf. on Image Processing Article (CrossRef Link) 157 - 160
Fridich J. , Goljian M. , Du R. 2002 “Lossless data embedding - new paradigm in digital watermarking” EURASIP Journal on Applied Signal Processing Article (CrossRef Link) 185 - 196    DOI : 10.1155/S1110865702000537
Fridich J. , Goljian M. , Du R. 2001 “Invertible authentication” in Proc. of SPIE Photonics West, Security and Watermarking of Multimedia Contents III San Jose, CA Article (CrossRef Link) 197 - 208
Goljan M. , Fridrich J. , Du R. 2001 “Distortion-free data embedding” in Proc. of 4th Information Hiding Workshop Pittsburgh, PA April Article (CrossRef Link) 27 - 41
Honsinger C. W. , Jones P. , Rabbani M. , Stoffel J. C. 2001 “Lossless recovery of an original image containing embedded data” US Patent 6278791 B1 Article (CrossRef Link).
Ni Z. , Shi Y. Q. , Ansari N. , Su W. 2006 “Reversible data hiding” IEEE Trans. on Circuits and Systems for Video Technology Article (CrossRef Link) 16 354 - 362    DOI : 10.1109/TCSVT.2006.869964
Tian J. 2003 “Reversible data embedding using a difference expansion” IEEE Trans. on Circuits and Systems for Video Technology Article (CrossRef Link) 13 890 - 896    DOI : 10.1109/TCSVT.2003.815962
Vleeschouwer C. D. , Delaigle J. F. , Macq B. 2001 “Circular interpretation of histograms for reversible watermarking” in Proc. of IEEE International Multimedia Signal Processing Workshop France October Article (CrossRef Link) 345 - 350
Huang H. C. , Wang F. H. , Pang J. S. 2001 “Efficient and robust watermarking algorithm with vector quantization” Electron. Lett. Article (CrossRef Link) 37 (13) 826 - 828    DOI : 10.1049/el:20010567
Huang H. C. , Wang F. H. , Pan J. S. 2002 “A VQ-based robust multi-watermarking algorithm” IEICE Trans. Fundam. Article (CrossRef Link) E-85A (7) 1719 - 1726
Lin C. Y. , Chang C. C. 2006 “Hiding data in VQ-compressed images using dissimilar pairs” J. Comput. Article (CrossRef Link) 17 (2) 3 - 10
Chang C. C. , Wu W. C. , Hu Y. C. 2007 “Lossless recovery of a VQ index table with embedded secret data” Journal of Visual Communication and Image Representation Article (CrossRef Link) 18 (3) 207 - 216    DOI : 10.1016/j.jvcir.2006.11.005
Yang C. H. , Lin Y. C. 2009 “Reversible data hiding of a VQ index table based on referred counts” Journal of Visual Communication and Image Representation Article (CrossRef Link) 20 (6) 399 - 407    DOI : 10.1016/j.jvcir.2009.04.001
Chen W. J. , Huang W. T. 2009 “VQ indices compression and information hiding using hybrid lossless index coding” Digital Signal Processing Article (CrossRef Link) 19 (3) 433 - 443    DOI : 10.1016/j.dsp.2008.11.003
Chang C. C. , Tai W. L. , Lin C. C. 2006 “ A reversible data hiding scheme based on side match vector quantization” IEEE Trans. on Circuits and Systems for Video Technology Article (CrossRef Link) 16 (10) 1301 - 1308    DOI : 10.1109/TCSVT.2006.882380
Chang C. C. , Kieu T. D. , Chou Y. C. 2009 “Reversible information hiding for VQ indices based on locally adaptive coding” Journal of Visual Communication and Image Representation Article (CrossRef Link) 20 (1) 57 - 64    DOI : 10.1016/j.jvcir.2008.08.005
Lin C. Y. , Chang C. C. 2006 “Hiding data in VQ-compressed images using dissimilar pairs” J. Comput. Article (CrossRef Link) 17 (2) 3 - 10
Chang C. C. , Lin C. Y. , Fan Y. H. 2008 “Lossless data hiding for color images based on block truncation coding” Pattern Recognition Article (CrossRef Link) 41 (7) 2347 - 2357    DOI : 10.1016/j.patcog.2007.12.009
Lin C. C. , Shiu P. F. 2010 “DCT-based reversible data hiding scheme” Journal of Software Article (CrossRef Link) 5 (2) 214 - 224    DOI : 10.4304/jsw.5.2.214-224
Chiou S. F. , Lu Y. C. , Liao I. E. , Hwang M. S. 2013 “An efficient reversible data hiding scheme based on SMVQ” The Imaging Science Journal Article (CrossRef Link) 61 (6) 467 - 474    DOI : 10.1179/1743131X12Y.0000000035
Chang C. C. , Nguyen T. S. , Lin C. C. 2013 “A reversible data hiding scheme for VQ indices using locally adaptive coding” The Journal of Systems and Software Article (CrossRef Link) 86 389 - 402    DOI : 10.1016/j.jss.2012.09.001