Designing a new reversible data hiding technique with a high embedding rate and a low compression rate for vector quantization (VQ) compressed images is encouraged. This paper proposes a novel lossless data hiding scheme for VQcompressed images based on the joint neighboring coding technique. The proposed method uses the difference values between a current VQ index and its left and upper neighboring VQ indexes to embed
n
secret bits into one VQ index, where
n
= 1, 2, 3, or 4. The experimental results show that the proposed scheme achieves the embedding rates of 1, 2, 3, and 4 bits per index (bpi) with the corresponding average compression rates of 0.420, 0.483, 0.545, and 0.608 bit per pixel (bpp) for a 256 sized codebook. These results confirm that our scheme performs better than other selected reversible data hiding schemes.
1. Introduction
T
he ability to transmit information securely has always been of great importance. As new ways and formats are developed for sending, storing, and representing information, novel methods must also be developed to ensure the security of sensitive information. In our highly connected world and with the prevalent use of public network channels for sending sensitive information, developing new methods to protect secret information from unauthorized entities is of paramount importance to both individuals and organizations.
Cryptography is one of the methods used for securing sensitive information
[1

3]
. It has proven to be a good method for securing information, however it has its own weakness. That is, the encrypted information is fully exposed during transmission. As a result, attackers can procure the encrypted data and decrypt it once the encryption method is known. In the case where the encryption method is not known, an attacker can still store the encrypted data and attempt to decrypt it at his leisure.
The information hiding (also called data hiding or data embedding) field seeks to protect sensitive information by hiding the fact that a message even exists
[4]
. This is done by hiding the sensitive data or secret message within another medium called a cover object that does not raise suspicion when transmitted
[5]
. Two areas of study have emerged within the information hiding field, namely digital watermarking and steganography
[6]
. In watermarking, the information embedded into a cover object (e.g., image, audio, video, or text) is pertinent to the cover object and is used to verify its validity. In steganography, however, the main purpose of the cover object is to hide the fact that covert communication is occurring.
All techniques developed within the steganographic and watermarking fields can be categorized into reversible (also called lossless, invertible, or distortionfree) and irreversible (also called lossy) techniques. Reversible techniques
[7

9]
are those that guarantee the perfect reconstruction of a cover object after a secret message has been extracted. Irreversible techniques cannot guarantee this
[10
,
11]
. Whether a reversible or irreversible technique is used in a particular situation depends on the application. If the cover object must be fully recovered such as for military or healthcare purposes, a reversible technique must be chosen. However, for situations where the full recovery of the cover object is not required, an irreversible technique may be applied.
Information hiding techniques can be applied to three domains, namely the spatial
[12

14]
, frequency (or transformed)
[15
,
16]
, and compressed
[17

22]
domains. In the spatial domain, information is hidden by modifying the amplitudes of the pixel values whereas in the frequency domain it is achieved by modifying the transformed coefficients. Many image compression algorithms have been used for storing and transmitting images across networks. Methods within the compressed domain such as vector quantization (VQ)
[23]
seek to embed secret information during the encoding of the VQ index table. Each domain has its own strengths and weaknesses with regard to embedding (or hiding) capacity, storage space, processing time, and other features. This article proposes a lossless data hiding system in the VQcompressed domain that is suitable to low bandwidth communication channels.
In 2009, Chang et al.
[24]
proposed a reversible information hiding scheme for VQ indices using joint neighboring coding (JNC). Their method hides one secret bit into a VQ index in raster scan order. The average embedding rate of this method is 0.984 bpi with a compression rate of 0.510 bpp for a 256 sized codebook. The main weakness of their method is that it embeds less than 1 bpi and their compression rate is greater than 0.5 bpp. Later in 2009, Wang and Lu
[25]
proposed a path optional lossless data hiding method also based on JNC to improve the embedding capacity of Chang et al.’s scheme
[24]
. Wang and Lu’s method uses two paths to allow a user to select the path 1 or 2 to conceal two or three secret bits into one VQ index, respectively. For a codebook of size 256, this scheme is able to achieve the average embedding rate of 1.953 bpi with the compression rate of 0.573 bpp for the first path and the average embedding rate of 2.884 bpi with the compression rate of 0.641 bpp for the second path. While there is an improvement in the embedding rate, the scheme however has a high compression rate. In 2013, Lee et al.
[26]
presented a lossless data hiding scheme that achieves the embedding rate of 2.952 bpi with the compression rate of 0.546 bpp for the 256 sized codebook. This scheme improves the embedding capacity and compression rate of the previous schemes
[24
,
25]
. Their scheme, however, degrades quickly as the codebook size is increased. The two schemes
[24
,
25]
were also improved by Kieu and Ramroach
[27]
. In this scheme, the first column and the first row of the VQ index table are used as the seed area. That is, there is no secret data embedding in this region. Consequently, the embedding rate and compression rate of this method can be further improved by eliminating the seed area.
To surmount the weaknesses of Chang et al.’s
[24]
, Wang and Lu’s
[25]
, and Lee et al.’s
[26]
methods, we propose a novel lossless data hiding scheme for VQcompressed images based on JNC. The proposed method conceals
n
secret bits, where
n
= 1, 2, 3, or 4, into each VQ index. The scheme achieves the various embedding rates of 1, 2, 3, and 4 bpi with compression rates of 0.420, 0.483, 0.545, and 0.608 bpp, respectively, based on the codebook sized 256. These results demonstrate that the proposed approach is better than previous methods
[24

26]
.
The rest of this paper unfolds in the following order. An overview of vector quantization, the methods proposed by Chang et al.
[24]
, Wang and Lu
[25]
, and Lee et al.
[26]
are covered in Section 2. The proposed method is then presented in Section 3. The experimental results are presented in Section 4, followed by a conclusion in Section 5.
2. Related Works
In this section, we present a review of the vector quantization (VQ) and Lee et al.’s method
[26]
.
 2.1 Vector Quantization
Vector quantization (VQ) is a lossy data compression method commonly used in image compression that is based on the block coding principle
[23]
. There are three steps associated with this method: codebook generation, VQ encoding, and VQ decoding. In the first step, the codebook
CB
containing
N
k
dimensional codewords
CW_{i}
’s is generated by using the LBG clustering algorithm
[28]
, where
i
= 0, 1, …,
N
 1 and
CW_{i}
= (
cw
_{i1}
,
cw
_{i2}
, …,
cw_{ik}
). The greyscale image
I
sized
H
×
W
to be compressed is then partitioned into nonoverlapping image block
B
’s sized
hs
×
ws
, where
hs
×
ws
=
k
(e.g.,
H
=
W
= 512,
N
= 256,
hs
=
ws
= 4,
k
= 16). In the second step, the VQ encoder takes each image block
B
in raster scan order and compresses it by examining the codebook
CB
and selecting the codeword
CW_{i}
with the minimum Euclidean distance from
B
. The index value of the selected codeword
CW_{i}
is then inserted into the VQ index table
T
sized (
H/hs
)×(
W/ws
) in raster scan order. The final step is the reconstruction of the original image
I
from the received VQ index table
T
and the codebook
CB
. Each block
B
of the original image is reconstructed by taking the respective VQ index in
T
and looking up the codeword
CW_{i}
associated with it.
 2.2 Lee et al.’s Method
Lee et al.
[26]
proposed a lossless data hiding method for VQ indices based on neighboring correlation. In general, the scheme embeds
r
or
v
secret bits from a secret message
S
into one VQ index of a VQ index table
T
sized (
H/hs
)×(
W/ws
) of a VQcompressed image
I
sized
H
×
W
, where
hs
×
ws
represents the image block size used during the VQ encoding process. In this scheme, the codewords in the codebook are sorted according to the mean values of the codewords before the VQ encoding is carried out. The VQ index table
T
is composed of (
H/hs
)×(
W/ws
) VQ indices
T
_{i,j}
’s, where
i
= 0, 1, ..., (
H/hs
)  1 and
j
= 0, 1, ..., (
W/ws
)  1. Lee et al.’s method uses a predefined parameter
z
that is half the length of the coarse subcodebook. The parameter
r
is the number of secret bits to be hidden in the case of a fine hit and
v
is the number of secret bits to be concealed in the case of a coarse hit. The values of
r
and
v
are calculated by
r
= ⎾log
_{2}
N
⏋  2,
v
= ⎾log
_{2}
N
⏋  3  ⎾log
_{2}
(2
z
)⏋, where
N
is the codebook size. Let
y
be the current VQ index to encode (i.e.,
y
=
T
_{i,j}
),
yl
be the VQ index to the left (i.e.,
yl
=
T
_{i,j1}
) and
yt
be the VQ index above (i.e.,
yt
=
T
_{i1,j}
). Additionally, let
fsb
0 and
fsb
1 be the fine subcodebooks associated with
yl
and
yt
, respectively, and let
csb
0 and
csb
1 be the coarse subcodebooks associated with
yl
and
yt
, respectively. These subcodebooks are defined by
fsb
0 = {
yl
},
fsb
1 = {
yt
},
csb
0 = {
yl

z
, ...,
yl
 1,
yl
+ 1, ...,
yl
+
z
}, and
csb
1 = {
yt

z
, ...,
yt
 1,
yt
+ 1, ...,
yt
+
z
}, respectively. If
y
belongs to
fsb
0 or
fsb
1, a fine hit state is obtained. If
y
belongs to
csb
0 or
csb
1, a coarse hit state is achieved, otherwise a miss state is obtained.
There are three main cases in their scheme. The first case occurs if
y
belongs to either
fsb
0 (i.e.,
y
=
yl
) or
fsb
0 (i.e.,
y
=
yt
) and this constitutes a fine hit. In this case, a 2bit indicator code 00 or 01 is appended to the output code stream
CS
, followed by the next
r
secret bits
s
_{1}
s
_{2}
...
s_{r}
from the secret stream
S
(i.e.,
CS
=
CS
00
s
_{1}
s
_{2}
...
s_{r}
or
CS
=
CS
01
s
_{1}
s
_{2}
...
s_{r}
). The second case is where
y
either exists in
csb
0 or
csb
1 and this constitutes a coarse hit. In this case, the log
_{2}
(2
z
)bit binary representation of the
y
’s position, denoted as
csbpos
, in the corresponding coarse subcodebook is recorded. If
y
exists in
csb
0, the bit stream 100
csbpos

s
_{1}
s
_{2}
...
s_{v}
is appended to the output code stream
CS
. If
y
exists in
csb
1, the bit stream 101
csbpos

s
_{1}
s
_{2}
...
s_{v}
is added to the output code stream
CS
. In the final case where
y
is not equal to
yl
or
yt
and does not belong to
csb
0 or
csb
1 (i.e., miss state), the bit stream 11
y
_{2}
is appended to the output code stream
CS
, where
y
_{2}
is the ⎾log
_{2}
N
⏋bit binary representation of
y
.
The above embedding procedure is continued until all remaining VQ indices of
T
are processed. The other details of this method can be found in
[26]
. Lee et al.’s approach performs very well for smooth images (e.g., Tiffany image) but it has a poor performance for complex images (e.g., Baboon image). In addition, the performance of this scheme degrades quickly when the codebook size
N
is greater than 128 (e.g.,
N
= 256, 512, and 1024).
3. The Proposed Method
 3.1 The Encoding and Embedding Phase
The large compression rates of Chang etal.’s
[24]
and Wang Lu et al.’s
[25]
schemes may arouse attackers’ suspicions. In this section, we present the proposed lossless data hiding scheme for VQ indexes based on joint neighboring coding
[24]
. The proposed scheme can embed
n
secret bits per VQ index in raster scan order, where
n
= 1, 2, 3 or 4. We limit the value of
n
to be less than or equal to 4 because for values of
n
greater than 4, the smallest average compression rate attainable is greater than 0.608 bpp for the codebook size
N
= 256. To increase the security of secret data distribution, it is supposed that the secret data has been encrypted by using a wellknown cryptosystem such as AES
[2]
before secret data hiding takes place. Therefore, even though adversaries can somehow extract the encrypted secret data from the output code stream, they still cannot comprehend the real information without also having a secure decryption key.
Firstly, a greyscale cover image
I
sized
H
×
W
is compressed by a VQ encoder that uses an
N
sized codebook
CB
containing
N
k
dimensional codewords (e.g.,
H
=
W
= 512,
N
= 256, and
k
= 16). The proposed method uses the codebook that is sorted as mentioned in Chang et al.’s method
[24]
. The result of which is a VQ index table
T
sized (
H/hs
)×(
W/ws
), where
hs
×
ws
is the image block size used by the VQ encoder (e.g.,
hs
=
ws
= 4). The VQ index table
T
= {
T
_{i,j}
}, where 0 ≤
i
≤
H/hs
 1, 0 ≤
j
≤
W/ws
 1, and 0 ≤
T
_{i,j}
≤
N
 1, is scanned in raster scan order for encoding and embedding. Secret data hiding occurs during the encoding of each VQ index. This process conceals
n
secret bits from the secret message
S
into each VQ index in
T
. The first VQ index
y
located at the first row and column of
T
(i.e.,
y
=
T
_{0,0}
) is converted to its ⎾log
_{2}
N
⏋bit binary representation
y
_{2}
. The first
n
secret bits
s
_{1}
s
_{2}
...
s_{n}
are then read from
S
and
y
is encoded by
y
_{2}

s
_{1}
s
_{2}
...
s_{n}
, where  denotes the concatenation operation. The encoded bit stream
y
_{2}

s
_{1}
s
_{2}
...
s_{n}
is then appended to the output code stream
CS
(i.e.,
CS
=
CS

y
_{2}

s
_{1}
s
_{2}
...
s_{n}
).
For all remaining VQ indices, the encoding and embedding process is performed as follows. The next VQ index
y
is read from
T
(i.e.,
y
=
T
_{i,j}
≠
T
_{0,0}
). In general, the encoding is performed on each VQ index by using two difference values
dl
and
du
, where
dl
is the difference between the VQ index to the left of
y
and
y
(i.e.,
dl
=
l

y
, where
y
=
T
_{i,j}
,
l
=
T
_{i,j1}
), and
du
is the difference between the VQ index directly above
y
and
y
(i.e.,
du
=
u

y
, where
y
=
T
_{i,j}
,
u
=
T
_{i1,j}
,). The VQ indexes in the first row of
T
(i.e.,
y
=
T
_{0,j}
where 1 ≤
j
≤
W/ws
 1), however, have no upper neighboring VQ indexes to calculate
du
and so
dl
is used in this case. That is, set
l
=
T
_{0,j1}
and
u
= l, the difference value
du
is then computed by
du
=
u

y
. Similarly, the VQ indexes in the first column of
T
(i.e.,
y
=
T
_{i,0}
where 1 ≤
i
≤
H/hs
 1) have no left neighboring VQ indexes to compute dl and so
du
is used in this case. That is, set
u
=
T
_{i1,0}
and
l
=
u
, the difference value
dl
is then computed by
dl
=
l

y
. The calculations of the difference values
dl
and
du
are shown in
Fig. 1
.
The calculations of difference values dl and du
The next
n
secret bits
s
_{1}
s
_{2}
...
s_{n}
are then read from
S
and the values of
dl
and
du
are examined. If either
dl
or
du
is equal to 0 (i.e., case 1: the VQ index to the left or above has the same value as the current VQ index
y
),
y
is encoded by
s
_{1}
s
_{2}
...
s_{n}
000 or
s
_{1}
s
_{2}
...
s_{n}
001, respectively. The encoded bit stream
s
_{1}
s
_{2}
...
s_{n}
000 or
s
_{1}
s
_{2}
...
s_{n}
001 is then appended to the code stream
CS
(i.e.,
CS
=
CS

s
_{1}
s
_{2}
...
s_{n}
000 or
CS
=
CS

s
_{1}
s
_{2}
...
s_{n}
001).
If
du
and
dl
are not equal to 0, only the value of
dl
is used to encode
y
. The absolute value of
dl
, denoted as 
dl
, ranges from 0 to
N
 1 inclusive. To represent
dl
requires
m
bits, where 1 ≤
m
≤ ⎾log
_{2}
N
⏋, the notation ⎾⏋ denotes the ceiling function, and
N
is the codebook size (e.g.,
N
= 256). As with previous schemes, a particular value of
m
is chosen as a threshold value.
In the case where 
dl
 cannot be represented in
m
bits (i.e., case 2: 
dl
 > 2
^{m}
 1),
y
is encoded by
s
_{1}
s
_{2}
...
s_{n}
01
y
_{2}
, where
y
_{2}
is the ⎾log
_{2}
N
⏋bit binary representation of
y
. The encoded bit stream
s
_{1}
s
_{2}
...
s_{n}
01
y
_{2}
is then appended to the code stream
CS
(i.e.,
CS
=
CS

s
_{1}
s
_{2}
...
s_{n}
01
y
_{2}
).
If
dl
is greater than or equal to (2
^{m}
 1) and less than 0 (i.e., case 3: (2
^{m}
 1) ≤
dl
< 0),
y
is encoded by
s
_{1}
s
_{2}
...
s_{n}
10(
dl
)
_{2}
, where (
dl
)
_{2}
is the
m
bit binary representation of the absolute value of
dl
. The encoded bit stream
s
_{1}
s
_{2}
...
s_{n}
10(
dl
)
_{2}
is then added to the code stream
CS
(i.e.,
CS
=
CS

s
_{1}
s
_{2}
...
s_{n}
10(
dl
)
_{2}
).
If
dl
is greater than 0 and less than or equal to 2
^{m}
 1 (i.e., case 4: 0 <
dl
≤ 2
^{m}
 1),
y
is encoded by
s
_{1}
s
_{2}
...
s_{n}
11
dl
_{2}
, where
dl
_{2}
is the
m
bit binary representation of
dl
. The encoded bit stream
s
_{1}
s
_{2}
...
s_{n}
11
dl
_{2}
is then sent to the code stream
CS
(i.e.,
CS
=
CS

s
_{1}
s
_{2}
...
s_{n}
11
dl
_{2}
).
The above encoding and embedding process is repeated for the next VQ index in raster scan order until all VQ indexes in the VQ index table
T
are processed. The proposed encoding and embedding method is summarized in
Table 1
. The flowchart of the proposed encoding and embedding scheme is shown in
Fig. 2
. The proposed encoding and embedding algorithm is described next.
Summary of the proposed encoding and embedding scheme
Summary of the proposed encoding and embedding scheme
The flow chart of the proposed encoding and embedding scheme.
The encoding and embedding algorithm
Input: A grayscale cover image
I
sized
H
×
W
, a codebook
CB
sized
N
, a secret message
S
, the preset values of
m
and
n
, where 1 ≤
m
≤ ⎾log
_{2}
N
⏋ and
n
= 1, 2, 3, or 4
Output: The binary code stream
CS
Step 1: Compress
I
by using a VQ encoder to obtain the VQ index table
T
sized (
H
/
hs
)×(
W
/
ws
), where
hs
×
ws
is the size of an image block used by the VQ encoder.
Step 2: Read the next VQ index
y
from the VQ index table
T
in raster scan order.
Step 3: If
y
is the topleft element of
T
(i.e.,
y
=
T
_{0,0}
), then
Step 3.1: Read the next
n
secret bits
s
_{1}
s
_{2}
...
s_{n}
from the secret message
S
.
Step 3.2: Append
y
_{2}

s
_{1}
s
_{2}
...
s_{n}
to
CS
(i.e.,
CS
=
CS

y
_{2}

s
_{1}
s
_{2}
...
s_{n}
),

wherey2is the ⎾log2N⏋bit binary representation ofyand the notation  denotes the concatenation operation.
Step 4: If
y
is not the topleft element of
T
(i.e.,
y
≠
T
_{0,0}
), then
Step 4.1: If
y
is located in the first row of
T
except
T
_{0,0}
(i.e.,
y
=
T
_{0,j}
where 1 ≤
j
<
W
/
ws
), then Set
l
to be the left neighboring VQ index of
y
(i.e.,
l
=
T
_{0,j1}
) and
u
=
l
.
Step 4.2: If
y
is positioned in the first column of
T
except
T
_{0,0}
(i.e.,
y
=
T
_{i,0}
where 1 ≤
i
<
H
/
hs
), then

Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti1,0) andl=u.
Step 4.3: If
y
is located from the second row and second column of
T
(i.e.,
y
=
T
_{i,j}
where 1 ≤
i
<
H
/
hs
and 1 ≤
j
<
W
/
ws
), then

Setlto be the left neighboring VQ index ofy(i.e.,l=Ti,j1).

Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti1,j).
Step 5: Read the next
n
secret bits
s
_{1}
s
_{2}
...
s_{n}
from the secret message
S
.
Step 6: Compute the difference values
dl
=
l

y
and
du
=
u

y
.
Step 7: If
dl
= 0 or
du
= 0 (i.e., case 1), then
Step 7.1: If
dl
equals 0 (i.e., case 1.1), then encode
y
by
s
_{1}
s
_{2}
...
s_{n}
000.

Append the bit streams1s2...sn000 toCS(i.e.,CS=CSs1s2...sn000).
Step 7.2: If
du
is equal to 0 (i.e., case 1.2), then encode
y
by
s
_{1}
s
_{2}
...
s_{n}
001.

Append the bit streams1s2...sn001 toCS(i.e.,CS=CSs1s2...sn001).
Step 8: Else if 
dl
 > 2
^{m}
 1 (i.e., case 2), then encode
y
by
s
_{1}
s
_{2}
...
s_{n}
01
y
_{2}
.

Append the bit streams1s2...sn01y2toCS(i.e.,CS=CSs1s2...sn01y2).
Step 9: Else if (2
^{m}
 1) ≤
dl
< 0 (i.e., case 3), then encode
y
by
s
_{1}
s
_{2}
...
s_{n}
10(
dl
)
_{2}
,

where (dl)2is thembit binary representation of the absolute value ofdl.

Append the bit streams1s2...sn10(dl)2toCS(i.e.,CS=CSs1s2...sn10(dl)2).
Step 10: Else (i.e., case 4: 0 <
dl
≤ 2
^{m}
 1) encode
y
by
s
_{1}
s
_{2}
...
s_{n}
11
dl
_{2}
,

wheredl2is thembit binary representation ofdl.

Append the bit streams1s2...sn11dl2toCS(i.e.,CS=CSs1s2...sn11dl2).
Step 11: Repeat steps 2 to 10 until all VQ indexes of the VQ index table
T
are processed.
Step 12: Output the binary code stream
CS
.
 3.2 The Decoding and Extracting Phase
The decoding and extracting process is the inverse process of the encoding and embedding process. At the receiving side, with the received code stream
CS
and
N
sized codebook
CB
, the decoder can extract the embedded secret message and restore the original VQ indices. The flowchart of the proposed decoding and extracting scheme is shown in
Fig. 3
. The summary of the proposed decoding and extracting algorithm is given below.
The flowchart of the proposed decoding and extracting scheme.
The decoding and extracting algorithm
Input: The binary code stream
CS
, the codebook
CB
sized
N
,

the preset values ofmandn, where 1 ≤m≤ ⎾log2N⏋ andn= 1, 2, 3, or 4
Output: The extracted secret message
S
and the reconstructed cover image
I’
sized
H
×
W
Step 1: Let the extracted secret message
S
and the recovered VQ index table
T
be empty.
Step 2: If the currently decoded VQ index
y
is the topleft element of
T
(i.e.,
y
is at the position
T
_{0,0}
), then
Step 2.1: Read the next ⎾log
_{2}
N
⏋ bits from
CS
and convert them into the decimal value
de
.
Step 2.2: Recover the original VQ index by
y
=
de
.
Step 2.3: Read the next
n
bits
c
_{1}
c
_{2}
...
c_{n}
from the code stream
CS
.
Step 2.4: Extract the
n
secret bits by
s
_{1}
s
_{2}
...
s_{n}
=
c
_{1}
c
_{2}
...
c_{n}
.
Step 2.5: Update the extracted secret message by
S
=
S

s
_{1}
s
_{2}
...
s_{n}
.
Step 3: If the currently decoded VQ index
y
is not the topleft element of
T
(i.e.,
y
is not at the location
T
_{0,0}
), then
Step 3.1: If the currently decoded VQ index
y
is located in the first row of
T
except the position
T
_{0,0}
(i.e.,
y
is at the position
T
_{0,j}
where 1 ≤
j
<
W/ws
), then

Setlto be the left neighboring VQ index ofy(i.e.,l=Ti,j1) andu=l.
Step 3.2: If the currently decoded VQ index
y
is positioned in the first column of
T
except the position
T
_{0,0}
(i.e.,
y
is at the position
T
_{i,0}
where 1 ≤
i
<
H/hs
), then

Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti1,j) andl=u.
Step 3.3: If the currently decoded VQ index
y
is located from the second row and second column of
T
(i.e.,
y
is located at
T
_{i,j}
where 1 ≤
i
<
H/hs
and 1 ≤
j
<
W/ws
), then

Setlto be the left neighboring VQ index ofy(i.e.,l=Ti,j1).

Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti1,j).
Step 4: Read the next
n
bits
c
_{1}
c
_{2}
...
c_{n}
from the code stream
CS
.
Step 5: Extract the
n
secret bits by
s
_{1}
s
_{2}
...
s_{n}
=
c
_{1}
c
_{2}
...
c_{n}
.

Update the extracted secret message byS=Ss1s2...sn.
Step 6: Read the next two bits
c
_{1}
c
_{2}
from the code stream
CS
.
Step 7: If
c
_{1}
c
_{2}
= 00 (i.e., case 1:
dl
= 0 or
du
= 0), then
Step 7.1: Read the next bit
c
_{3}
from the code stream
CS
.
Step 7.2: If
c
_{3}
= 0 (i.e., case 1.1:
dl
= 0), then recover the original VQ index by
y
=
l
.
Step 7.3: Else (i.e.,
c
_{3}
= 1, case 1.2:
du
= 0), then restore the original VQ index by
y
=
u
.
Step 8: Else if
c
_{1}
c
_{2}
= 01 (i.e., case 2: 
dl
 > 2
^{m}
 1), then

Read the next ⎾log2N⏋ bits fromCSand convert them into the decimal valuede.

Reconstruct the original VQ index byy=de.
Step 9: Else (i.e., case 3: (2
^{m}
 1) ≤
dl
< 0 or case 4: 0 <
dl
≤ 2
^{m}
 1)

Read the nextmbits fromCSand convert them into the decimal valuedl.

Ifc1c2= 10 (i.e., case 3: (2m 1) ≤dl< 0), then setdl= dl.
Recover the original VQ index by
y
=
l

dl
.
Step 10: Insert the restored VQ index
y
to the VQ index table
T
in raster scan order.
Step 11: Repeat steps 3 to 10 until all bits of the code stream
CS
are processed.
Step 12: Restore the cover image
I’
sized
H
×
W
from the constructed VQ index table
T
sized (
H/hs
)×(
W/ws
) by using the VQ decoder.
4. Experimental Results and Discussion
The proposed scheme was implemented by using Microsoft Visual C++ 2010 software running on the Intel Core i7, 2.2 GHz CPU, and 6 GB RAM hardware platform. The binary secret message
S
was randomly generated by using the rand() function. Seven grayscale cover images all sized 512×512 were used to test the previous and proposed schemes and are shown in
Fig. 4
.
Grayscale cover images used in performance tests
Sorted codebooks of sizes
N
= 128, 256, 512, and 1024 consisting of 16dimensional codewords were used to generate the VQ index tables for each test image (i.e.,
k
=
hs
×
ws
= 16). The performances of the proposed method for the values of
n
= 1, 2, 3, and 4 (denoted as P1, P2, P3, and P4, respectively) are compared to Chang et al.’s scheme
[24]
, Wang and Lu’s scheme
[25]
, and Lee et al.’s scheme
[26]
.
In order to evaluate the performance of the proposed scheme, four criteria, compression rate measured in bit per pixel (bpp), embedding rate measured in bits per index (bpi), embedding efficiency, and visual quality of reconstructed images were used. The compression rate is defined by
CR
= 
CS
 /
H
×
W
(bpp), where 
CS
 is the length of the output code stream
CS
and
H
×
W
represents the number of pixels in the original cover image. The embedding rate is defined by
ER
= 
S
 /
NI
(bpi), where 
S
 is the total number of secret bits that can be embedded into a VQ index table and
NI
is the number of indices in the VQ index table (i.e.,
NI
= (
H/hs
)×(
W/ws
)).
The embedding efficiency (
EE
) is the number of secret bits embedded when one bit of the output code stream
CS
is transmitted. The embedding efficiency is defined by
EE
= 
S
 / 
CS
 =
ER
/ (
CR
×
hs
×
ws
), where
hs
×
ws
is the size of an image block used by the VQ encoder.
 4.1 Experiments on Selecting Appropriate Parametersmandz
The compression rate performance of Chang et al.’s scheme
[24]
, Wang and Lu’s scheme
[25]
, and the proposed scheme is affected by the preset value of the parameter
m
that is used to represent the difference value
d
in the binary representation. The performances with regard to the embedding rate and compression rate of Lee et al.’s scheme
[26]
depend on the predetermined value of the parameter
z
that is used for the coarse subcodebooks. The impact of the preset values of the parameter
m
on the proposed scheme are presented in
Tables 2

5
. and that of the parameter
z
on Lee et al.’s method are shown in
Tables 6

9
in the appdenix.
The effect of different values ofmon compression rate of the proposed scheme withn= 1, 2, 3, and 4 for the codebook sizeN= 128
The effect of different values of m on compression rate of the proposed scheme with n = 1, 2, 3, and 4 for the codebook size N = 128
The effect of different values ofmon compression rate of the proposed scheme withn= 1, 2, 3, and 4 for the codebook sizeN= 256
The effect of different values of m on compression rate of the proposed scheme with n = 1, 2, 3, and 4 for the codebook size N = 256
The effect of different values ofmon compression rate of the proposed scheme withn= 1, 2, 3, and 4 for the codebook sizeN= 512
The effect of different values of m on compression rate of the proposed scheme with n = 1, 2, 3, and 4 for the codebook size N = 512
The effect of different values ofmon compression rate of the proposed scheme withn= 1, 2, 3, and 4 for the codebook sizeN= 1024
The effect of different values of m on compression rate of the proposed scheme with n = 1, 2, 3, and 4 for the codebook size N = 1024
It can be seen from
Tables 2

9
that to obtain the optimal (i.e., smallest value) compression rate with the codebooks of sizes
N
= 128, 256, 512, and 1024, the selected values of the parameter
m
for the proposed scheme are
m
= 4, 4, 5 and 6, respectively. For Lee et al.’s scheme
[26]
, the parameter
z
is chosen so that the scheme achieves its maximum embedding rate. Thus, the suggested values of the parameter
z
for this method are
z
= 2, 4, 8 and 16, respectively.
 4.2 Comparing the Proposed Scheme with Previous Schemes
In this section, we compare the performance results of the proposed scheme with the schemes proposed by Chang et al.
[24]
, Wang and Lu
[25]
with paths 1 and 2 as well as Lee et al.
[26]
. The comparative results among the simulated methods with regard to average embedding rate
ER
, compression rate
CR
, and embedding efficiency
EE
for the codebooks of sizes
N
= 128, 256, 512 and 1024 are shown in
Table 10
. It is noted that, the codebook sizes
N
= 128, 256, 512, and 1024, the selected values of the parameter
m
for Chang et al.’s scheme
[24]
are
m
= 1, 4, 6, and 7, respectively. The suitable values of the parameter
m
for Wang and Lu’s scheme
[25]
with the path 1 are
m
= 2, 3, 5, and 6, respectively. The proper values of the parameter
m
for Wang and Lu’s scheme
[25]
with the path 2 are
m
= 2, 4, 5, and 6, respectively.
Results of averageER(bpi),CR(bpp), andEEof simulated methods with their selected values ofmandzfor codebook sizesN= 128, 256, 512, and 1024 and test images inFig. 4
Results of average ER (bpi), CR (bpp), and EE of simulated methods with their selected values of m and z for codebook sizes N = 128, 256, 512, and 1024 and test images in Fig. 4
While both Chang et al.’s scheme
[24]
and the proposed scheme with
n
= 1 produce embedding rates near 1 bpi, the method P1 achieves a true 1 bpi while Chang et al.’s scheme obtains 0.984 bpi. Chang et al.’s scheme does not achieve 1 bpi as it uses the first row and first column as a seed area and does not embed secret data in this area. Additionally, P1 achieves the embedding rate of 1 bpi with significantly lower compression rates than Chang et al.’s scheme across all codebook sizes tested as can be seen in
Table 10
. The reason for Chang et al.’s high compression rates is due to the fact that this scheme uses
m
padding bits 0’s when the difference value
d
= 0 or 
d
 > 2
^{m}
 1. With respect to the embedding efficiency,
Table 10
demonstrates that the embedding efficiencies of the scheme P1 are higher than those of Chang et al.’s scheme
[24]
regardless of the codebook sizes. This confirms the superiority of the scheme P1 over Chang et al.’s scheme.
A similar trend can be seen from
Table 10
when comparing Wang and Lu’s scheme
[25]
with the path 1 which produces near 2 bpi to the scheme P2. Wang and Lu’s method with the path 1 produces the embedding rate of 1.953 bpi while P2 produces a true 2 bpi. As can be seen from
Table 10
, the method P2 achieves a slightly higher embedding rate with much smaller compression rates regardless of the codebook sizes. The higher compression rates of Wang and Lu’s scheme
[25]
with the path 1 are also due to the use of
m
padding bits 0’s in the case where the difference value
d
= 0. For the embedding efficiency comparison,
Table 10
indicates that the embedding efficiencies obtained by Wang and Lu’s method
[25]
with the path 1 are 0.242, 0.213, 0.191, and 0.175 whereas those attained by the method P2 are 0.298, 0.259, 0.227, and 0.205. This demonstrates that the scheme P2 surpasses Wang and Lu’s scheme with the path 1.
Both Wang and Lu’s scheme
[25]
with the path 2 and Lee et al.’s scheme
[26]
produce embedding rates around 3 bpi and are comparable with the scheme P3.
Table 10
shows that Wang and Lu’s scheme and P3 both have the constant embedding rates of 2.884 bpi and 3 bpi, respectively, regardless of the codebook sizes. Lee et al.’s method, however, has the variable embedding rates of 3.128, 2.952, 2.740, and 2.679 bpi for the codebooks of sizes 128, 256, 512, and 1024, respectively.
From
Table 10
we can see that Wang and Lu’s scheme
[25]
with the path 2 has a lower embedding rate than the scheme P3. This is due to the fact that their scheme requires a large seed area (i.e., first two rows, first two columns, and the rightmost column of the VQ index table) whereas P3 truly embeds secret data into every VQ index. Wang and Lu’s scheme with the path 2 also has much higher compression rates across all codebook sizes. This is because the utilization of the neighboring VQ indices in computing the difference value
d
by Wang and Lu’s scheme leads to a large value of
d
. In addition,
m
padding bits 0’s are used by this scheme when the difference value
d
= 0. In terms of the embedding efficiency, it can be observed from
Table 10
that the embedding efficiencies achieved by Wang and Lu’s method
[25]
with the path 2 are 0.315, 0.281, 0.255, and 0.236, those gained by Lee et al.’s
[26]
scheme are 0.412, 0.338, 0.280, and 0.249, and those obtained by P3 are 0.388, 0.344, 0.306, and 0.278. Thus, it can be deduced that the embedding efficiency of the scheme P3 is superior to that of Wang and Lu’s method
[25]
with the path 2. We can see from
Table 10
that, for the 128 sized codebook, Lee et al.’s method has the
EE
value of 0.412 which is better than the P3’s result of 0.388 for the same codebook size. This is supported by their slightly higher embedding rate of 3.128 bpi versus 3 bpi for P3 and a better compression rate of 0.475 bpp versus 0.483 bpp for P3. For the three remaining codebooks, however, the scheme P3 has the better
EE
values of 0.344, 0.306, and 0.278 whereas the
EE
values of Lee et al.’s method are 0.338, 0.280, and 0.249. This is due to the fact that Lee et al.’s scheme embeds less secret data when the codebook size increases whereas our scheme remains the constant embedding rate regardless of the codebook size. Additionally, with the exception of the 128 sized codebook, the compression rate of our method stays within 0.001 of theirs. Thus, it can be concluded that the performance of Lee et al.’s method is better than that of the scheme P3 for the 128 sized codebook and the scheme P3 has a better performance than Lee et al.’s scheme for the codebooks sized 256, 512, and 1024.
Lee et al.’s method
[26]
has an excellent performance in terms of the embedding rate, compression rate, and embedding efficiency for smooth images such as the Tiffany image, as shown in
Table 11
. For the Tiffany image, their method is capable of attaining the embedding rates of 4.345, 4.281, 4.186, and 4.275 bpi at the compression rates of 0.444, 0.515, 0.585, and 0.642 bpp for the codebooks sized 128, 256, 512, and 1024, respectively. Thus, it is clear that Lee et al.’s method surpasses the scheme P3 for smooth images. As can be seen from
Table 11
, however, Lee et al.’s method performs poorly when applied to complex images (e.g., Baboon image) and this effect worsens as the codebook size increases. We can clearly see this from the results of the Baboon image. Thus, it can be said that the scheme P3 is superior to Lee et al.’s method for complex images.
Comparative results of Lee et al.’s scheme[26]and P3 for smooth image Tiffany and complex image Baboon
Comparative results of Lee et al.’s scheme [26] and P3 for smooth image Tiffany and complex image Baboon
None of the previous schemes
[24

26]
achieves average embedding rates around 4 bpi. From
Table 10
, we can see that, for the 128 sized codebook, the scheme P4 achieves the embedding rate of 4 bpi at the average compression rate of 0.545 bpp that is within an acceptable range. Even though for the codebook of size 256, the scheme P4 has a higher compression rate of 0.608 bpp for the embedding rate of 4 bpi. Thus, we believe that this is still viable.
Table 10
further shows that there is a jump in the compression rate for the 512 and 1024 sized codebooks, making use of P4 at these codebook sizes less alluring.
The visual quality of the reconstructed images was evaluated by using peak signaltonoise ratio (
PSNR
) which is defined as follows.
The
MSE
(mean square error) is the difference between the original cover image
I
sized
H
×
W
and the reconstructed image
I’
sized
H
×
W
, and
I
(
i
,
j
) and
I’
(
i
,
j
) are the values of the pixels located at the
i
th row and
j
th column of
I
and
I’
, respectively. Because the simulated schemes reversibly conceal secret bits into VQ indices in a VQ index table, the original VQ indices can be completely recovered. Therefore, the
PSNR
values of the simulated methods are the same as those of the VQ compression method.
Fig. 5
shows the
PSNR
values of the simulated schemes for the codebook size
N
= 256.
Visual quality results of restored cover images of simulated schemes.
5. Conclusion
In this paper, we propose a novel lossless data hiding method for VQ indices based on joint neighboring coding. The proposed method embeds n secret bits into one VQ index, where
n
= 1, 2, 3, 4. The proposed approach can obtain the embedding rates of 1, 2, 3, and 4 bpi. Using the embedding efficiency
EE
as a fair comparison factor among the simulated methods, our method surpasses the three previous works, namely Chang et al.’s
[24]
and Wang and Lu’s
[25]
schemes for all codebook sizes except Lee et al.’s method
[26]
for the 128 sized codebook. Thus, we can conclude that our method is a viable method for use in a data hiding application such as digital libaries or secret communications.
BIO
Andrew Rudder received the B.S. degree in Computer Science in 2003 and M.S. degree in Computer Science in 2006 from The University of the West Indies, St. Augustine, Trinidad and Tobago. Currently, he is a Ph.D. candidate in Computer Science at The University of the West Indies, St. Augustine, Trinidad and Tobago. Since 2007, he has been with the Department of Computing and Information Technology, Faculty of Science and Technology, The University of the West Indies, St. Augustine, Trinidad and Tobago, where he is currently an assistant Lecturer. His research interests include information hiding, data compression, and image processing.
The Duc Kieu received the B.S. degree in Mathematics from the University of Pedagogy, Vietnam, in 1995, the B.S. degree in Information Technology from the University of Natural Sciences, Vietnam, in 1999, the M.S. degree in Computer Science from Latrobe University, Australia, in 2005, and the Ph.D. degree in Computer Science from Feng Chia University, Taiwan, in 2009. Since 2010, he has been with the Department of Computing and Information Technology, Faculty of Science and Technology, The University of the West Indies, St. Augustine, Trinidad and Tobago, where he is currently a Lecturer. His research interests include information hiding, data compression, and image processing.
Rivest R.
,
Shamir A.
,
Adleman L.
1978
“A method for obtaining digital signatures and publickey cryptosystems,”
Communications of the ACM
21
(2)
120 
126
DOI : 10.1145/359340.359342
Cox I.
,
Miller M.
,
Bloom J.
,
Fridrich J.
,
Kalker T.
2007
Digital watermarking and steganography
2nd Edition
Morgan Kauffman
Bender W.
,
Gruhl D.
,
Morimoto N.
,
Lu A.
1996
“Techniques for data hiding,”
IBM Systems Journal
35
(34)
313 
336
DOI : 10.1147/sj.353.0313
Petitcolas F.A.P.
,
Anderson R.J.
,
Kuhn M.G.
“Information hiding  a survey,”
in Proc. of IEEE Special Issue on Protection of Multimedia Content
1999
vol. 87, no. 7
1062 
1078
Hu Y.
,
Lee H.
,
Li J.
2009
“DEbased reversible data hiding with improved overflow location map,”
IEEE Transactions on Circuits and Systems for Video Technology
19
(2)
250 
260
DOI : 10.1109/TCSVT.2008.2009252
Coltuc D.
2012
“Low distortion transform for reversible watermarking,”
IEEE Transactions on Image Processing
21
(1)
412 
417
DOI : 10.1109/TIP.2011.2162424
Yang C.H.
,
Weng C.Y.
,
Wang S.J.
,
Sun H.M.
2008
“Adaptive data hiding in edge areas of images with spatial LSB domain systems,”
IEEE Transactions on Information Forensics and Security
3
(3)
488 
497
DOI : 10.1109/TIFS.2008.926097
Hong W.
,
Chen T.S.
2012
“A novel data embedding method using adaptive pixel pair matching,”
IEEE Transactions on Information Forensics and Security
7
(1)
176 
184
DOI : 10.1109/TIFS.2011.2155062
Tian J.
2003
“Reversible data embedding using a difference expansion,”
IEEE Transactions on Circuits and Systems for Video Technology
13
(8)
831 
841
DOI : 10.1109/TCSVT.2003.815951
Alattar A.M.
2004
“Reversible watermark using the difference expansion of a generalized integer transform,”
IEEE Transactions on Image Processing
13
(8)
1147 
1156
DOI : 10.1109/TIP.2004.828418
Thodi D.M.
,
Rodriguez J. J.
2007
“Expansion embedding techniques for reversible watermarking,”
IEEE Transactions on Image Processing
16
(3)
721 
730
DOI : 10.1109/TIP.2006.891046
Zhang X.
,
Wang S.
,
Qian Z.
,
Feng G.
2010
“Reversible fragile watermarking for locating tampered blocks in JPEG images,”
Signal Processing
90
(12)
3026 
3036
DOI : 10.1016/j.sigpro.2010.04.027
Chang C.C.
,
Pai P.Y.
,
Yeh C.M.
,
Chan Y.K
2010
“A high payload frequencybased reversible image hiding method,”
Information Sciences
180
(11)
2286 
2298
DOI : 10.1016/j.ins.2010.01.034
Pan J.S.
,
Sung M.T.
,
Huang H.C.
,
Liao B.Y.
2004
“Robust VQbased digital watermarking for the memoryless binary symmetric channel,”
IEICE Transactions on Fundamentals
E87A
(7)
1839 
1841
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
20
(6)
399 
407
DOI : 10.1016/j.jvcir.2009.04.001
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
20
(1)
57 
64
DOI : 10.1016/j.jvcir.2008.08.005
Yang C.H.
,
Lin Y.C.
2010
“Fractal curves to improve the reversible data embedding for VQindexes based on locally adaptive coding,”
Journal of Visual Communication and Image Representation
21
(4)
334 
342
DOI : 10.1016/j.jvcir.2010.02.008
Chang C.C.
,
Nguyen T.S.
,
Lin C.C
2011
“A reversible data hiding for VQ indices using locally adaptive coding,”
Journal of Visual Communication and Image Representation
22
(7)
664 
672
DOI : 10.1016/j.jvcir.2011.06.005
Kieu T.D.
,
Rudder A.
,
Goodridge W.
2014
“A reversible steganographic scheme for VQ indices based on locally adaptive coding,”
Journal of Visual Communication and Image Representation
25
(6)
1378 
1386
DOI : 10.1016/j.jvcir.2014.06.001
Chang C.C.
,
Kieu vT.D.
,
Wu W.C.
2009
“A lossless data embedding technique by joint neighboring coding,”
Pattern Recognition
42
(7)
1597 
1603
DOI : 10.1016/j.patcog.2008.11.040
Wang J.X.
,
Lu Z.M.
2009
“A path optional lossless data hiding scheme based on VQ joint neighboring coding,”
Information Sciences
179
(19)
3332 
3348
DOI : 10.1016/j.ins.2009.05.021
Lee J.D.
,
Chiou Y.H.
,
Guo J.M.
2013
“Lossless data hiding for VQ indices based on neighboring correlation,”
Information Sciences
221
419 
438
DOI : 10.1016/j.ins.2012.09.020
Kieu T.D.
,
Ramroach S.
2015
“A reversible steganographic scheme for VQ indices based on joint neighboring coding,”
Expert Systems with Applications
42
(2)
713 
722
DOI : 10.1016/j.eswa.2014.09.001
Linde Y.
,
Buzo A.
,
Gray R.M.
1980
“An algorithm for vector quantizer design,”
IEEE Transactions on Communications
28
(1)
84 
95
DOI : 10.1109/TCOM.1980.1094577