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).
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 stegoimage. 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 stegoimage 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 stegomedia because the stegomedia 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 VQbased or SMVQbased 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 VQcompressed 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 VQbased 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 VQgenerated indices. Then, Yang and Lin’s VQbased reversible data hiding scheme is introduced.
 2.1 Vector quantization
In 1984, Gray
[3]
proposed vector quantization, also called VQ. The VQ technique is wellknown for both its lossy data compression and its efficient clustering. The main idea behind VQ is that the
k
dimensional space
R^{k}
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 wellknown iterative generalized Lloyd algorithm also called LindeBuzoGray algorithm (LBG)
[3]
is often used to generate codebooks for VQ. As
Fig. 1
shows, in VQ, an image is first decomposed into several nonoverlapping 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}
, …,
x_{k}
) is compared with the codewords in the codebook to determine the nearest codeword, which is based on the Euclidian distance defined in Equation (1).
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):
where
x_{j}
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'
=
× 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
=
. In this scheme, half of the indices in
Y’
are used to embed secret data and at least 2
^{B1}
indices are used as indicators. For an image
I
, each block
I_{i}
is encoded into index
y
_{i}
by VQ coding.
y_{i}
is then transformed into
y_{i}’
, where
y_{i}’
is the corresponding index in a group and sometimes includes an indicator. To better explain Yang and Lin’s scheme, the function
tranj
(
y_{i}
) is used to represent the transformation function, where
y_{i}
is transformed into the corresponding index in group
C_{j}
.
Fig. 2
shows an example of Yang and Lin’s scheme when
B
is 1. In Yang and Lin’s scheme, if index
y_{i}
belongs to group
C_{0}
,
y_{i}'
is set to
trans_{0}
(
y_{i}
) when secret bit
s
=0 is hidden and
y_{i}'
is set to
trans_{1}
(
y_{i}
) when secret bit
s
=1 is hidden. If the index
y
_{i}
belongs to group
C_{1}
, indicator
I_{0}
is added ahead by setting
y_{i}'
to
I_{0}
║
trans_{1}
(
y_{i}
), and no secret data is hidden.
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}
,…,
s_{r}
), where
s_{j}
= {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,
C_{0}
, and
C_{1}
.
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
∈
C_{0}
, and
s
=0,
y
is unchanged by setting
y'
=
trans_{0}(y)
.
Step 4:
If
y
∈
C_{0}
, and
s
=1, transfer
y
to group
C_{1}
by setting
y'
=
trans_{1}(y)
.
Step 5:
If
y
∈
C_{1}
, no secret data is hidden, and
y
is transferred by setting
y'
=
I_{0}
║
trans_{1}(y)
, where
I_{0}
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,
C_{0}
, and
C_{1}
, 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,
C_{0}
, and
C_{1}
.
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
=
trans_{0} (y')
and 1bit secret data
s
is extracted according to the following rules. If
y'
∈
C_{k}
, then
s
=
k
(i.e., if
y'
∈
C_{1}
,
s
=1. Otherwise, if
y'
∈
C_{0}
,
s
=0).
Step 3:
If
y'
has indicator
I_{0}
and
y'
=
I_{0}
║
y"
recover
y
by using the formula
y
=
trans_{1} (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
_{n1}
) , and the secret message is denoted as
^{S = (s0,s1,…,sr)}
, where
^{sj = {0,1}}
and 0
^{≤ j ≤ r}
. 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.
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}
,…,
v_{k}
, where
k
is the size of the index table.
Nine basic scan paths
After the sequence of index values
v
_{1}
,
v
_{2}
,…,
v_{k}
is obtained according to the determined scan path, a sequence of adjacent index differences,
D
= {
d
_{1}
,
d
_{2}
,…,
d_{k}
}, is calculated by using Equation (2). Adjacent index difference
d_{i}
can be a negative or positive value.
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 2bit indicator, 1 bit a sign of the difference value and a 4bit 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.
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 8bit binary representation of the absolute value of
d
, and “║” represents the concatenation operation.
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}
s_{2}
are read from the secret message
B
.
Step 5.1:
If
d
= 0, encode
d
by
r
=01║
s
_{1}
s_{2}
and concatenate
r
into code stream
CS
.
Step 5.2:
If 1 ≤
d
≤ 3, encode
d
by
r
=10║
sign
(
d
)║
w_{2}
, 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
w_{2}
is the 4bit binary representation of
w
. Finally, concatenate
r
into code stream
CS
.
Step 5.3:
If 4 ≤
d
≤ 11, encode
d
by
r
=11║
sign
(
d
)║
q_{2}
, 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
q_{2}
is the 6bit binary representation of
q
. Finally, concatenate
r
into code stream
CS
.
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.
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 2bit indicator should be “10”, and the two secret bits
s_{1}s_{2}
=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
s_{1}s_{2}
=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
.
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
s_{1}s_{2}
. The original difference index
d
is recovered as 0. Then concatenate
s_{1}s_{2}
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).
Two secret bits
s_{1}s_{2}
is extracted by using Equation (7).
Then, send
d
to sequence
D
and concatenated
s_{1}s_{2}
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).
After that, extract 2 secret bits
s_{1}s_{2}
by using Equation (9).
Then, the original difference index value
d
is sent to the sequence of adjacent indices’ differences
D
, and
s_{1}s_{2}
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 nonoverlapping image block was 4×4, with each block a 16dimensional vector. The codebook used in our experiments was sized 256 and was trained by using the wellknown 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 1GB RAM. The operating system was Windows 7 Professional and our algorithm was programmed by Microsoft Visual Studio 2005 C#.
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).
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.
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.
where ║
S
║ is the number of bits that can be embedded into a cover image and
N_{IDX}
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
.
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 signaltonoise (
PSNR
) ratio is used to evaluate image quality, as shown in Equation (12).
where the mean square error (
MSE
) for a
W
×
H
grayscale image is defined as in Equation (13).
where
I_{ij}
and
I^{’}_{ij}
are the pixel values of the cover and stegoimages, respectively. However, our scheme, Chang et al.’s schemes and Yang and Lin’s scheme are all VQbased 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
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
ChinChen 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.
ThaiSon 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.
ChiaChen 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, ShaLu, Taiwan. Her research interests include image and signal processing, image data hiding, mobile agent, and electronic commerce.
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
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 significantbit 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 VQbased image hiding scheme”
Pattern Recognition
Article (CrossRef Link)
2
1051 
1058
DOI : 10.1016/S01678655(01)000447
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
Thien C. C.
,
Lin J. C.
2003
“A simple and high hiding capacity method for hiding digitbydigit data in images based on modulus function”
Pattern Recognition
Article (CrossRef Link)
36
2875 
2881
DOI : 10.1016/S00313203(03)002218
Wang R. Z.
,
Lin C.F.
,
Lin J. C.
2000
“Hiding data in images by optimal moderately significantbit 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/S00313203(00)000157
Zhang X.
,
Wang S.
2005
“Steganography using multiplebase 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
“Distortionfree 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 VQbased robust multiwatermarking algorithm”
IEICE Trans. Fundam.
Article (CrossRef Link)
E85A
(7)
1719 
1726
Lin C. Y.
,
Chang C. C.
2006
“Hiding data in VQcompressed 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 VQcompressed 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
“DCTbased reversible data hiding scheme”
Journal of Software
Article (CrossRef Link)
5
(2)
214 
224
DOI : 10.4304/jsw.5.2.214224
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