Advanced
A Lossless Data Hiding Scheme for VQ Indexes Based on Joint Neighboring Coding
A Lossless Data Hiding Scheme for VQ Indexes Based on Joint Neighboring Coding
KSII Transactions on Internet and Information Systems (TIIS). 2015. Aug, 9(8): 2984-3004
Copyright © 2015, Korean Society For Internet Information
  • Received : January 11, 2015
  • Accepted : June 23, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Andrew Rudder
The Duc Kieu

Abstract
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 VQ-compressed 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.
Keywords
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 distortion-free) 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 VQ-compressed 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 VQ-compressed 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 CWi ’s is generated by using the LBG clustering algorithm [28] , where i = 0, 1, …, N - 1 and CWi = ( cw i1 , cw i2 , …, cwik ). The greyscale image I sized H × W to be compressed is then partitioned into non-overlapping 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 CWi with the minimum Euclidean distance from B . The index value of the selected codeword CWi 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 CWi 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 VQ-compressed 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 sub-codebook. 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,j-1 ) and yt be the VQ index above (i.e., yt = T i-1,j ). Additionally, let fsb 0 and fsb 1 be the fine sub-codebooks associated with yl and yt , respectively, and let csb 0 and csb 1 be the coarse sub-codebooks associated with yl and yt , respectively. These sub-codebooks 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 2-bit indicator code 00 or 01 is appended to the output code stream CS , followed by the next r secret bits s 1 s 2 ... sr from the secret stream S (i.e., CS = CS ||00|| s 1 s 2 ... sr or CS = CS ||01|| s 1 s 2 ... sr ). 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 sub-codebook is recorded. If y exists in csb 0, the bit stream 100|| csbpos || s 1 s 2 ... sv is appended to the output code stream CS . If y exists in csb 1, the bit stream 101|| csbpos || s 1 s 2 ... sv 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 well-known 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 ... sn are then read from S and y is encoded by y 2 || s 1 s 2 ... sn , where || denotes the concatenation operation. The encoded bit stream y 2 || s 1 s 2 ... sn is then appended to the output code stream CS (i.e., CS = CS || y 2 || s 1 s 2 ... sn ).
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,j-1 ), 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 i-1,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,j-1 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 i-1,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 .
PPT Slide
Lager Image
The calculations of difference values dl and du
The next n secret bits s 1 s 2 ... sn 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 ... sn ||000 or s 1 s 2 ... sn ||001, respectively. The encoded bit stream s 1 s 2 ... sn ||000 or s 1 s 2 ... sn ||001 is then appended to the code stream CS (i.e., CS = CS || s 1 s 2 ... sn ||000 or CS = CS || s 1 s 2 ... sn ||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 ... sn ||01|| y 2 , where y 2 is the ⎾log 2 N ⏋-bit binary representation of y . The encoded bit stream s 1 s 2 ... sn ||01|| y 2 is then appended to the code stream CS (i.e., CS = CS || s 1 s 2 ... sn ||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 ... sn ||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 ... sn ||10||(- dl ) 2 is then added to the code stream CS (i.e., CS = CS || s 1 s 2 ... sn ||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 ... sn ||11|| dl 2 , where dl 2 is the m -bit binary representation of dl . The encoded bit stream s 1 s 2 ... sn ||11|| dl 2 is then sent to the code stream CS (i.e., CS = CS || s 1 s 2 ... sn ||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
PPT Slide
Lager Image
Summary of the proposed encoding and embedding scheme
PPT Slide
Lager Image
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 top-left element of T (i.e., y = T 0,0 ), then
Step 3.1: Read the next n secret bits s 1 s 2 ... sn from the secret message S .
Step 3.2: Append y 2 || s 1 s 2 ... sn to CS (i.e., CS = CS || y 2 || s 1 s 2 ... sn ),
  • wherey2is the ⎾log2N⏋-bit binary representation ofyand the notation || denotes the concatenation operation.
Step 4: If y is not the top-left 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,j-1 ) 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=Ti-1,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,j-1).
  • Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti-1,j).
Step 5: Read the next n secret bits s 1 s 2 ... sn 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 ... sn ||000.
  • Append the bit streams1s2...sn||000 toCS(i.e.,CS=CS||s1s2...sn||000).
Step 7.2: If du is equal to 0 (i.e., case 1.2), then encode y by s 1 s 2 ... sn ||001.
  • Append the bit streams1s2...sn||001 toCS(i.e.,CS=CS||s1s2...sn||001).
Step 8: Else if | dl | > 2 m - 1 (i.e., case 2), then encode y by s 1 s 2 ... sn ||01|| y 2 .
  • Append the bit streams1s2...sn||01||y2toCS(i.e.,CS=CS||s1s2...sn||01||y2).
Step 9: Else if -(2 m - 1) ≤ dl < 0 (i.e., case 3), then encode y by s 1 s 2 ... sn ||10||(- dl ) 2 ,
  • where (-dl)2is them-bit binary representation of the absolute value ofdl.
  • Append the bit streams1s2...sn||10||(-dl)2toCS(i.e.,CS=CS||s1s2...sn||10||(-dl)2).
Step 10: Else (i.e., case 4: 0 < dl ≤ 2 m - 1) encode y by s 1 s 2 ... sn ||11|| dl 2 ,
  • wheredl2is them-bit binary representation ofdl.
  • Append the bit streams1s2...sn||11||dl2toCS(i.e.,CS=CS||s1s2...sn||11||dl2).
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.
PPT Slide
Lager Image
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 top-left 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 ... cn from the code stream CS .
Step 2.4: Extract the n secret bits by s 1 s 2 ... sn = c 1 c 2 ... cn .
Step 2.5: Update the extracted secret message by S = S || s 1 s 2 ... sn .
Step 3: If the currently decoded VQ index y is not the top-left 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,j-1) 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=Ti-1,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,j-1).
  • Setuto be the upper neighboring VQ index ofy(i.e.,u=Ti-1,j).
Step 4: Read the next n bits c 1 c 2 ... cn from the code stream CS .
Step 5: Extract the n secret bits by s 1 s 2 ... sn = c 1 c 2 ... cn .
  • Update the extracted secret message byS=S||s1s2...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 .
PPT Slide
Lager Image
Grayscale cover images used in performance tests
Sorted codebooks of sizes N = 128, 256, 512, and 1024 consisting of 16-dimensional 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 sub-codebooks. 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 signal-to-noise ratio ( PSNR ) which is defined as follows.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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.
References
Davis R.M. 1978 “The data encryption standard in perspective,” IEEE Communications Magazine 16 (6) 5 - 9    DOI : 10.1109/MCOM.1978.1089771
Wright M.A. 2001 “The advanced encryption standard,” Network Security 2001 10 11 - 13    DOI : 10.1016/S1353-4858(01)01018-2
Rivest R. , Shamir A. , Adleman L. 1978 “A method for obtaining digital signatures and public-key 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 (3-4) 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 “DE-based 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
Peng F. , Li X. , Yang B. 2014 “Improved PVO-based reversible data hiding,” Digital Signal Processing 25 255 - 265    DOI : 10.1016/j.dsp.2013.11.002
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 frequency-based 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 VQ-based digital watermarking for the memoryless binary symmetric channel,” IEICE Transactions on Fundamentals E-87A (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 VQ-indexes 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
Gray R.M. 1984 “Vector quantization,” IEEE ASSP Magazine 1 (2) 4 - 29    DOI : 10.1109/MASSP.1984.1162229
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