# Separable Reversible Data Hiding in Encrypted VQ-Encoded Images

Authors: Fang Cao; Yujie Fu; Heng Yao; Mian Zou; Jian Li; Chuan Qin
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In this paper, a reversible data-hiding scheme in encrypted, vector quantization (VQ) encoded images is proposed. During image encryption, VQ-encoded image, including codebook and index table, is encrypted by content owner with stream-cipher and permutation to protect the privacy of image contents. As for additional-data embedding, a baseline method is first proposed and its corresponding optimized method is then given. By grouping one high-occurrence index with one or multiple low-occurrence indices, a series of index groups are constructed. Thus, by modifying the high-occurrence index to the corresponding index within the same group according to the current to-be-embedded bits, data embedding can be realized. The optimal hiding capacity is obtained by optimizing the coefficient vector for different types of index groups. Separable operations of data extraction, image decryption, and recovery can be achieved on the receiver side based on the availability of the encryption and data-hiding keys. Experimental results show that our scheme can achieve high hiding capacity and satisfactory directly decrypted image quality and guarantee security and reversibility simultaneously.


---

## Body

## 1. Introduction

With the rapid development of digital communication and signal processing, a large amount of multimedia data, such as image, video, and audio, are transmitted on networks. However, secure management for multimedia data with privacy protection is an inevitable issue and also is one meaningful research topic. Reversible data-hiding (RDH) is an emerging technique which has greatly attracted researchers’ interests in recent years [1–4]. As for the RDH technique, data hider can embed additional data into cover image reversibly, which means the original cover image can be completely recovered after extracting the embedded data. Some representative RDH schemes, such as difference expansion (DE) [1], histogram shifting (HS) [2], and prediction-error expansion (PEE) [3], have been proposed in the past few years. In addition to the RDH schemes for gray scale images, there are a lot of RDH schemes developed for color images [5], compressed images [6], and halftone images [7].Vector quantization (VQ) is an effective image encoding method, which can be utilized for image compression [8]. During the process of VQ encoding, the original uncompressed image Io is first divided into a series of nonoverlapping blocks. For each image block, Euclidean distances between the block with the L code words in the trained codebook C are calculated, and the index of the code word with the minimum Euclidean distance is recorded into the index table T as the encoded result for the current block. During VQ decoding, according to the indices in the index table T, all image blocks can be easily decoded as the corresponding code words in the codebook C to form the VQ-decoded image I. Figure 1 illustrates an example of VQ-encoded image, in which a gray scale image with the size of M × N is compressed to an index table sized M/n × N/n, where n × n is the size of divided blocks. Each value in the index table, corresponding to one n × n block, can be represented with log2L bits. Thus, for the whole image, the compression ratio can be calculated as 8 × n2/log2L. Generally speaking, a codebook with more code words, i.e., larger L, can lead to better visual quality of VQ-decoded image.Figure 1
An example of VQ-encoded image.In recent years, a number of RDH schemes have been developed for VQ-encoded images in the plaintext form [9–16]. Chang et al. proposed a RDH scheme in VQ-encoded images based on a de-clustering strategy [9], in which two de-clustering methods were used with the minimum-spanning-tree and a short-spanning-path. Lee et al. modified VQ-encoded images by the side-matched VQ (SMVQ) technique to form a transformed image, and exploited the distribution of this transformed image to achieve high hiding capacity and low bit rate [10]. Kieu and Ramroach utilized the joint neighboring coding method to realize reversible steganographic scheme for VQ indices [12], in which the differences between the current index; the left, upper, and top-left neighboring indices; and their combinations were used to hide additional bits. In Ref. [15], two RDH schemes for VQ-encoded images were proposed based on switching-tree coding and dynamic-tree coding. These two schemes performed data embedding by choosing one of the possible index encoding ways when multiple ways were available to encode the index, and the outputted codes can be decoded to original VQ index table with the conventional decoder. Pan and Wang proposed a RDH scheme for two-stage VQ-encoded image based on search-order coding (SOC) in Ref. [16]. SOC can employ the correlation of indices to obtain better compression ratio, thus, the combination of SOC and data hiding in this scheme can achieve both high performances for compression ratio and hiding capacity.Due to the current prosperity of cloud storing and computing, a vast amount of personal data are stored and processed on the cloud to alleviate computation burden on user clients [17, 18]. But, in order to protect user privacy, it is better to first encrypt user data before uploading onto cloud. Thereby, for the convenience of data management and retrieval, RDH in encrypted images (RDHEI) has attracted extensive interest in the field of multimedia security. According to when the space for accommodating additional data was created, i.e., before or after image encryption, embedding mechanisms of most RDHEI schemes can be categorized into two types: vacating room after encryption (VRAE) [19–28] and reserving room before encryption (RRBE) [29–34]. In addition, some researchers introduced homomorphic encryption (HE) into RDHEI [35–38], which can realize the operations of data embedding directly in encrypted domain. A brief review of the related works on RDHEI is given in Section 2.In this work, we focus on RDH in encrypted, VQ-encoded image. An encryption method for VQ-encoded image is first designed for the codebook and the index table, respectively. Before conducting additional-data embedding in the encrypted index table, all VQ indices are sorted according to their occurrence numbers. A baseline method of data embedding is proposed based on constructing index groups for one high-occurrence index and one low-occurrence index each time, and then we improve the baseline method through generalized index grouping for multiple low-occurrence indices. By modifying the high-occurrence index to the corresponding index within the same group according to the current to-be-embedded bits, additional-data embedding can be achieved, and the optimal hiding capacity is obtained by optimizing coefficient vector for different types of index groups. Separable operations of data extraction, image decryption, and recovery can be realized on the receiver side based on the availability of the encryption and data-hiding keys. The proposed scheme can achieve satisfactory performances of hiding capacity and directly decrypted image quality and guarantee security and reversibility simultaneously.The remaining parts of the paper are organized as follows. Section2 gives a brief review of related works about RDHEI. Section 3 introduces the baseline of the proposed scheme, including image encryption, additional-data embedding, data extraction, and image recovery. Section 4 gives performance optimization for additional-data embedding procedure of the baseline method in Section 3, which consists of generalized index grouping, multiple-bits embedding, and hiding capacity optimization. Section 5 presents experimental results and analysis. Conclusions are drawn in Section 6.


## 2. Related Works

An effective RDHEI framework can be described as: the content-owner encrypts the original image with encryption key and then sends the encrypted image to the data hider; the data hider embeds additional data into the encrypted image with data-hiding key to produce the marked, encrypted image; and the authorized receiver implements data extraction, image decryption, and image recovery on the marked, encrypted image according to encryption key and data-hiding key. In the following, three main categories of RDHEI schemes are briefly reviewed.


### 2.1. VRAE-Based Schemes

In Ref. [19], the encrypted image with stream cipher was segmented into a number of nonoverlapping blocks, and by flipping the three LSBs of different parts of pixels, one bit of additional data can be embedded into each block. The receiver can achieve data extraction and image recovery through estimation with a fluctuation function. Hong et al. improved the order of data extraction and block recovery and introduced a side-match strategy to increase the accuracy of the extracted data and recovered image [20]. Liao and Shu utilized the absolute mean difference of neighboring pixels to measure the recovery accuracy of image blocks after decryption [21]. Different from Refs. [19–21] that data extraction must be conducted after image decryption, a separable RDHEI scheme was proposed in Ref. [22], which means that the operations of image decryption and data extraction can be realized on the receiver side independently. A public key modulation mechanism was employed in Ref. [23] to achieve data embedding without accessing the secret encryption key. In addition, a powerful two-class SVM classifier was presented to differentiate the encrypted and nonencrypted patches, leading to recovering the embedded data and original image correctly. Huang et al. proposed to encrypt the original image in a blockwise manner [24], which can retain the correlation within the pixels of each encrypted block. Then, traditional RDH methods in plaintext images can be used in encrypted image for data hiding. In Ref. [25], a RDHEI scheme with an adaptive encoding strategy was presented, which adaptively compressed the MSB layers of embeddable blocks according to occurrence frequency of MSB and then embedded additional data together with reversed Huffman codewords and auxiliary data. Yi and Zhou first presented a parametric binary tree labeling (PBTL) algorithm to label pixels in two different types, and then, they proposed a PBTL-RDHEI scheme in encrypted images, which can achieve data embedding by pixel labeling and bit replacement effectively [28].


### 2.2. RRBE-Based Schemes

In order to avoid the errors on data extraction or image recovery, Ma et al. proposed a scheme by reserving room before encryption with a traditional RDH method in Ref. [29], which can acquire the complete reversibility. In Ref. [30], some pixels in the original plaintext image were first predicted before encryption, thus, additional data can then be embedded in the prediction errors. A benchmark encryption algorithm was applied to the rest pixels and a specific encryption algorithm was designed to encrypt prediction errors. Cao et al. considered that an image patch can be linearly represented by some atoms in an over-complete dictionary through sparse coding [31], and the residual errors can be encoded and self-embedded in the original image. Thereby, a large extra room can be created before image encryption, and the data hider can embed more additional data into the encrypted image based on this strategy of patch-level sparse representation. Puteaux et al. proposed a new reversible method with most significant bit (MSB) prediction [32], which can achieve a high hiding capacity. During the preprocessing, a location map was produced by detecting prediction errors. Through MSB substitution, additional data can be embedded and the embedding rate was close to 1 bpp. Yin et al. proposed a RDHEI scheme based on multi-MSB prediction and Huffman coding [33]. Before image encryption with a stream cipher, multi-MSB of each pixel was predicted and marked with Huffman coding in the original image as the preprocessing. Thus, additional data can be embedded into the encrypted image through multi-MSB substitution.


### 2.3. HE-Based Schemes

Chen et al. proposed a RDH scheme for encrypted signals based on Paillier public key encryption, and applied it on digital images [35], in which each pixel value was divided into two parts encrypted, respectively. Then, two encrypted LSBs of each pixel pair were modified to hide one bit with the help of homomorphism. In Wu et al.’s scheme [36], each unit in the original image was segmented into three components with energy transfer equation, and each component was encrypted by Paillier homomorphic encryption. The data hider can embed additional bits into the encrypted image by using the properties of Paillier homomorphism. A separable RDHEI scheme based on additive homomorphism and pixel value ordering (PVO) was given in Ref. [37]. Additive homomorphism applied in this scheme can guarantee that the performance of embedding rate for PVO in an encrypted domain can approximate to that in plaintext domain without involving data expansion. In Ref. [38], Xiang and Luo proposed to form mirroring ciphertext groups (MCGs) by replacing encrypted host pixels with encrypted reference pixels in the same group. In an MCG, the reference ciphertext pixel remained unchanged as a reference while the data hider can embed additional data into the LSBs of host encrypted pixels with homomorphic multiplication.The abovementioned RDHEI schemes mainly focused on the encrypted, uncompressed gray scale image. In addition, some schemes have also been designed for other kinds of cover data, such as JPEG-encoded image [39–41], palette image [42], 2D vector graphic [43], and 3D mesh model [44], in the encrypted domain. However, to the best of our knowledge, there are few reported works about RDHEI of VQ-encoded images currently.


## 2.1. VRAE-Based Schemes

In Ref. [19], the encrypted image with stream cipher was segmented into a number of nonoverlapping blocks, and by flipping the three LSBs of different parts of pixels, one bit of additional data can be embedded into each block. The receiver can achieve data extraction and image recovery through estimation with a fluctuation function. Hong et al. improved the order of data extraction and block recovery and introduced a side-match strategy to increase the accuracy of the extracted data and recovered image [20]. Liao and Shu utilized the absolute mean difference of neighboring pixels to measure the recovery accuracy of image blocks after decryption [21]. Different from Refs. [19–21] that data extraction must be conducted after image decryption, a separable RDHEI scheme was proposed in Ref. [22], which means that the operations of image decryption and data extraction can be realized on the receiver side independently. A public key modulation mechanism was employed in Ref. [23] to achieve data embedding without accessing the secret encryption key. In addition, a powerful two-class SVM classifier was presented to differentiate the encrypted and nonencrypted patches, leading to recovering the embedded data and original image correctly. Huang et al. proposed to encrypt the original image in a blockwise manner [24], which can retain the correlation within the pixels of each encrypted block. Then, traditional RDH methods in plaintext images can be used in encrypted image for data hiding. In Ref. [25], a RDHEI scheme with an adaptive encoding strategy was presented, which adaptively compressed the MSB layers of embeddable blocks according to occurrence frequency of MSB and then embedded additional data together with reversed Huffman codewords and auxiliary data. Yi and Zhou first presented a parametric binary tree labeling (PBTL) algorithm to label pixels in two different types, and then, they proposed a PBTL-RDHEI scheme in encrypted images, which can achieve data embedding by pixel labeling and bit replacement effectively [28].


## 2.2. RRBE-Based Schemes

In order to avoid the errors on data extraction or image recovery, Ma et al. proposed a scheme by reserving room before encryption with a traditional RDH method in Ref. [29], which can acquire the complete reversibility. In Ref. [30], some pixels in the original plaintext image were first predicted before encryption, thus, additional data can then be embedded in the prediction errors. A benchmark encryption algorithm was applied to the rest pixels and a specific encryption algorithm was designed to encrypt prediction errors. Cao et al. considered that an image patch can be linearly represented by some atoms in an over-complete dictionary through sparse coding [31], and the residual errors can be encoded and self-embedded in the original image. Thereby, a large extra room can be created before image encryption, and the data hider can embed more additional data into the encrypted image based on this strategy of patch-level sparse representation. Puteaux et al. proposed a new reversible method with most significant bit (MSB) prediction [32], which can achieve a high hiding capacity. During the preprocessing, a location map was produced by detecting prediction errors. Through MSB substitution, additional data can be embedded and the embedding rate was close to 1 bpp. Yin et al. proposed a RDHEI scheme based on multi-MSB prediction and Huffman coding [33]. Before image encryption with a stream cipher, multi-MSB of each pixel was predicted and marked with Huffman coding in the original image as the preprocessing. Thus, additional data can be embedded into the encrypted image through multi-MSB substitution.


## 2.3. HE-Based Schemes

Chen et al. proposed a RDH scheme for encrypted signals based on Paillier public key encryption, and applied it on digital images [35], in which each pixel value was divided into two parts encrypted, respectively. Then, two encrypted LSBs of each pixel pair were modified to hide one bit with the help of homomorphism. In Wu et al.’s scheme [36], each unit in the original image was segmented into three components with energy transfer equation, and each component was encrypted by Paillier homomorphic encryption. The data hider can embed additional bits into the encrypted image by using the properties of Paillier homomorphism. A separable RDHEI scheme based on additive homomorphism and pixel value ordering (PVO) was given in Ref. [37]. Additive homomorphism applied in this scheme can guarantee that the performance of embedding rate for PVO in an encrypted domain can approximate to that in plaintext domain without involving data expansion. In Ref. [38], Xiang and Luo proposed to form mirroring ciphertext groups (MCGs) by replacing encrypted host pixels with encrypted reference pixels in the same group. In an MCG, the reference ciphertext pixel remained unchanged as a reference while the data hider can embed additional data into the LSBs of host encrypted pixels with homomorphic multiplication.The abovementioned RDHEI schemes mainly focused on the encrypted, uncompressed gray scale image. In addition, some schemes have also been designed for other kinds of cover data, such as JPEG-encoded image [39–41], palette image [42], 2D vector graphic [43], and 3D mesh model [44], in the encrypted domain. However, to the best of our knowledge, there are few reported works about RDHEI of VQ-encoded images currently.


## 3. Baseline of the Proposed Scheme

Figure2 presents the framework of the proposed scheme for RDH in encrypted VQ-encoded images. As shown in Figure 2(a), on the content-owner side, with encryption key Ke = {Ke1, Ke2}, encryption for VQ-encoded image can be divided into two steps: codebook encryption and index table encryption, respectively. Then, after receiving the encrypted, VQ-encoded image, through index grouping and data-hiding key Kh, additional data can be embedded on the data-hider side, see Figure 2(b). On the receiver side, we can extract additional data and restore the VQ-encoded image. It can be seen from Figure 2(c) that additional data can be extracted with data-hiding key Kh; receiver can obtain a decrypted image which is similar to the original image with encryption key Ke; when the receiver has both encryption key Ke and data-hiding key Kh, the embedded data can be successfully extracted and the VQ-encoded image can also be perfectly recovered. Details of our baseline scheme are introduced as follows.Figure 2
Framework of the proposed scheme. (a) VQ-encoded image encryption, (b) additional-data embedding, (c) data extraction and image recovery.
(a)(b)(c)


### 3.1. VQ-Encoded Image Encryption

As we know, a VQ-encoded image consists of one codebookC and an index table T. Hence, in order to guarantee the security, VQ-encoded image encryption can be divided into two parts, i.e., codebook encryption and index table encryption.Suppose VQ codebookC contains L code words, and in each code word, there are n2 decimal values. Denote Pi,j as the jth value of the ith code word in the codebook C, where i = 1, 2, …, L, j = 1, 2, …, n2, and the value of Pi,j can be represented as eight binary bits:(1)Pi,j,k=Pi,j2k−1mod2,k=1,2,…,8,where Pi,j,k denotes the kth bit of Pi,j. A sequence of pseudo-random bits Si,j,k (i = 1, 2, …, L, j = 1, 2, …, n2, k = 1, 2, …, 8) is generated with encryption key Ke1. The operation of bitwise exclusive-or (XOR) is performed on all L code words for codebook encryption:(2)Pi,j,ke=Pi,j,k⊕Si,j,k,Pi,je=∑k=18Pi,j,ke⋅2k−1,where Pi,j(e) denotes the jth encrypted value in the ith code word after stream-cipher encryption. After all code words in the codebook C are encrypted, the encrypted codebook Ce is obtained.As for the index tableT sized M/n × N/n, all the index values in T are permuted with the encryption key Ke2.(3)Te=permT,Ke2,where perm(·) denotes the permutation function, and Te is the encrypted index table. The security can be guaranteed because the codebook C is encrypted by the stream cipher while permuting the index table T. The key space of index table permutation can be calculated as (M/n × N/n)! As for an original uncompressed image sized 512 × 512 (M = N = 512), when block size is chosen as 4 × 4 (n = 4), the whole key space of index table permutation is: [(512/4) × (512/4)]! = 16384! The codebook encryption based on stream cipher can be considered to further strengthen the security of encryption, even when the permutation key Ke2 is leaked or cracked. After the VQ-encoded image encryption for codebook and index table, Ce and Te are transmitted to the data-hider side together for additional-data embedding.


### 3.2. Additional-Data Embedding

In our scheme, after receivingCe and Te, data hider first counts the occurrence numbers of VQ indices in the encrypted index table Te. Initially, the occurrence numbers of indices corresponding to all L code words in the encrypted codebook Ce are set as zero. When a VQ index is scanned in Te, its occurrence number is increased by one. That is to say, for the VQ index k, its occurrence number γk (k = 1, 2, …, L) can be calculated as:(4)γk=∑x=1M/n∑y=1N/nϕk,Tx,y,where Tx,y denotes the index value at coordinate (x, y) in the index table Te, and φ(·) is a counting function returning 1 or 0. When the current VQ index Tx,y is equal to k, φ returns 1; otherwise, φ returns 0. Generally, occurrence numbers of VQ indices in the index table are not uniform for a natural image. Figure 3 shows the distribution of occurrence numbers of VQ indices (L = 128) for image Lena, in which X axis and Y axis denote the index values and their corresponding occurrence numbers, respectively. We can observe from Figure 3 that some VQ indices occur frequently while some VQ indices are not used at all.Figure 3
Histogram of VQ index values for imageLena (L = 128).After scanning the whole index tableTe, the L different kinds of VQ indices are sorted according to their corresponding occurrence numbers γk (k = 1, 2, …, L) in the descending order. In the proposed scheme, VQ indices with higher and lower occurrence numbers are utilized to achieve additional-data embedding. Note that the distribution of VQ indices is not changed before and after VQ-encoded image encryption in our scheme. The procedure of additional-data embedding includes two stages: (1) index grouping and (2) data embedding, which are described in detail as follows.


#### 3.2.1. A Index Grouping

Denote the sortedL VQ indices as c1, c2, …, cL, and their corresponding occurrence numbers are γ1, γ2, …, γL. We define the index set {cα, cα+ 1, …, cL} with lower occurrence numbers as Φ, where α is a threshold satisfying γα ≤ σ, and σ is a pre-determined parameter, which is discussed in Section 5. The relationship between α and σ can be represented as:(5)α=argminiγi≤σ.In addition to the VQ indices inΦ, the VQ indices with higher occurrence numbers are selected as another set Θ = {c1, c2, …, cβ}, and their corresponding index occurrence numbers are γ1, γ2, …, γβ, where β is set to L − α + 1. The remaining indices are formed as the set Ω = {cβ+1, cβ+2, …, cα−1}.In the following, VQ indices from the two setsΦ and Θ are exploited to construct β index groups through an iterative strategy. In detail, the β index groups are emptied initially. Then, the index with the highest occurrence number, denoted as cgj, in the current set Θ and the index with the lowest occurrence number, denoted as csj, in the current set Φ are selected to form one index group {cgj, csj}, j = 1, 2, …, β, and the two indices, cgj and csj, are removed from Θ and Φ, respectively. According to the above way, β index groups can be constructed iteratively until the two sets Θ and Φ become empty.


#### 3.2.2. Data Embedding

In order to guarantee the reversibility of original VQ-encoded image on the receiver side, side information should be recorded for the indices inΦ whose occurrence numbers are not zero, i.e., ci∈Φ and γi ≠ 0, i∈ {α, α + 1, …, L}. In detail, for the jth index group {cgj, csj}, j = 1, 2, …, β, we first utilize log2(MN/n2) bits to sequentially represent the occurrence number of the index csj in Te; if the occurrence number of the index csj in Te, i.e., γi corresponding to ci∈Φ, does not equal 0, we should further utilize γi·log2(MN/n2) bits to record the position information of the γi indices in Te. Thus, the length of side information is:(6)ρ=β+∑i=αLγi⋅log2MNn2.We compress the side information by run-length coding and concatenate the compressed side information with the additional dataw to be embedded together as w′ after scrambling with the data-hiding key Kh. During data embedding, for each index group {cgj, csj}, if the occurrence number of the index csj in Te is not equal to 0, data hider should replace all the index values csj in Te with the indices cm that can be randomly selected from the set Ω, and the modified index table is denoted as Te′. Then, each VQ index in Te′ that is equal to the index cgj with higher occurrence number in one of the β index groups, i.e., {cgj, csj}, can be embedded with one binary bit. In detail, data hider scans the VQ indices in Te′ with the raster-scanning order, and if the current scanning index Tx,y is equal to cgj in the jth index group (j = 1, 2, …, β), one binary bit wi from w′ can be embedded by:(7)Tx,y′=cgj,ifwi=0,csj,ifwi=1,where Tx,y′denotes the marked VQ index. In other words, for the current scanning index Tx,y belonging to the set Θ, if the to-be-embedded bit is 0, Tx,y remains unchanged, otherwise, Tx,y is changed to its corresponding index with lower occurrence number in the same index group.After all VQ indices, belonging toΘ, in Te′ finish the above procedure, we can obtain a marked, encrypted index table Tew. Then, Tew and Ce are transmitted to the receiver for data extraction and image recovery. Note that the β index groups should also be sent to the receiver as auxiliary data ℜ.


### 3.3. Data Extraction and Image Recovery

When the receiver obtains the marked, encrypted index tableTew, the encrypted codebook Ce and the auxiliary data ℜ, data extraction and image recovery can be conducted. There are three scenarios: (1) if the receiver only has the data-hiding key Kh, the additional data w can be extracted correctly; (2) if the receiver only has the encryption key Ke, a directly decrypted index table Td, which is similar to the original index table T can be obtained; and (3) if the receiver has both Ke and Kh, additional data w and original index table T can both be recovered with no error. Details are presented as follows.


#### 3.3.1. Data Extraction

First, the two index setsΘ and Φ corresponding to higher and lower occurrence numbers can be easily obtained based on the auxiliary data ℜ representing the β index groups. Then, during scanning the index table Tew in the raster-scanning order, according to the current scanning index Tx,y′ belonging to Θ or Φ, the embedded bit wi′ can be extracted sequentially, see equation (8).(8)wi′=0,ifTx,y′∈Θ,1,ifTx,y′∈Φ,no data extracted,other wise.Concatenating all extracted bitswi′, the embedded data w′ can be obtained correctly. Then, the receiver inversely scrambles w′ through the data-hiding key Kh, and parses the ρ-bits side information from w′, thus, the remaining part is the extracted additional data w.


#### 3.3.2. Image Decryption

If the receiver only has the encryption keyKe = {Ke1, Ke2}, he/she can first generate the sequence of pseudo-random bits Si,j,k (i = 1, 2, …, L, j = 1, 2, …, n2, k = 1, 2, …, 8) by Ke1, which is the same with the one on the content-owner side. Through decrypting based on XOR operation, the decrypted codebook Cd can be obtained, which is exactly the same as the original codebook C.On the other hand, the receiver scans the marked, encrypted index tableTew, and if the current scanning index Tx,y′ is equal to csj in one of the β index groups (j = 1, 2, …, β), Tx,y′ is modified as the corresponding cgj in the same group. After all indices in Tew are performed, a new index table Te′ can be produced. Then, through decrypting Te′ based on permutation with Ke2, a directly decrypted index table Td, which is similar to the original index table T, can be obtained. If required, a directly decrypted image Id can also be acquired through decoding the index table Td by the VQ codebook C.As we know, the side information records the numbers and the positions for the indices inΦ with nonzero occurrence numbers, and these indices are replaced by cm randomly selected in Ω during data embedding. Therefore, due to the unavailability of the data-hiding key Kh, the side information cannot be parsed from w′, which means these recorded indices cannot be recovered from cm in Ω to csj in Φ. In other words, without Kh, Te′ cannot be recovered to Te perfectly, and Td is not exactly the same with T.


#### 3.3.3. Image Recovery

If both encryption keyKe and data-hiding key Kh are available, the receiver can obtain the index table Te′ and can also parse the ρ-bits side information and the additional data w from the extracted data w′ with Kh. According to the parsed side information, the receiver can know the detailed numbers and positions for the indices in Φ with nonzero occurrence numbers, which are replaced by cm randomly selected in Ω during data embedding. Thus, through scanning the index table Te′, the indices at the positions indicated in the side information can be restored from cm to the corresponding index csj (whose occurrence number is not zero) in the index group{cgj, csj}. As a result, the index table Te′ is recovered to Te perfectly, and after decrypting Te based on permutation with Ke2, the original index table T can be recovered reversibly. As described previously, the original codebook C can be obtained through decrypting Cd with Ke1 based on XOR operation. Therefore, the additional data w, original index table T, and original codebook C can all be acquired when both Ke and Kh are available. If required, the original VQ-decoded image I can also be acquired through decoding T by C.


## 3.1. VQ-Encoded Image Encryption

As we know, a VQ-encoded image consists of one codebookC and an index table T. Hence, in order to guarantee the security, VQ-encoded image encryption can be divided into two parts, i.e., codebook encryption and index table encryption.Suppose VQ codebookC contains L code words, and in each code word, there are n2 decimal values. Denote Pi,j as the jth value of the ith code word in the codebook C, where i = 1, 2, …, L, j = 1, 2, …, n2, and the value of Pi,j can be represented as eight binary bits:(1)Pi,j,k=Pi,j2k−1mod2,k=1,2,…,8,where Pi,j,k denotes the kth bit of Pi,j. A sequence of pseudo-random bits Si,j,k (i = 1, 2, …, L, j = 1, 2, …, n2, k = 1, 2, …, 8) is generated with encryption key Ke1. The operation of bitwise exclusive-or (XOR) is performed on all L code words for codebook encryption:(2)Pi,j,ke=Pi,j,k⊕Si,j,k,Pi,je=∑k=18Pi,j,ke⋅2k−1,where Pi,j(e) denotes the jth encrypted value in the ith code word after stream-cipher encryption. After all code words in the codebook C are encrypted, the encrypted codebook Ce is obtained.As for the index tableT sized M/n × N/n, all the index values in T are permuted with the encryption key Ke2.(3)Te=permT,Ke2,where perm(·) denotes the permutation function, and Te is the encrypted index table. The security can be guaranteed because the codebook C is encrypted by the stream cipher while permuting the index table T. The key space of index table permutation can be calculated as (M/n × N/n)! As for an original uncompressed image sized 512 × 512 (M = N = 512), when block size is chosen as 4 × 4 (n = 4), the whole key space of index table permutation is: [(512/4) × (512/4)]! = 16384! The codebook encryption based on stream cipher can be considered to further strengthen the security of encryption, even when the permutation key Ke2 is leaked or cracked. After the VQ-encoded image encryption for codebook and index table, Ce and Te are transmitted to the data-hider side together for additional-data embedding.


## 3.2. Additional-Data Embedding

In our scheme, after receivingCe and Te, data hider first counts the occurrence numbers of VQ indices in the encrypted index table Te. Initially, the occurrence numbers of indices corresponding to all L code words in the encrypted codebook Ce are set as zero. When a VQ index is scanned in Te, its occurrence number is increased by one. That is to say, for the VQ index k, its occurrence number γk (k = 1, 2, …, L) can be calculated as:(4)γk=∑x=1M/n∑y=1N/nϕk,Tx,y,where Tx,y denotes the index value at coordinate (x, y) in the index table Te, and φ(·) is a counting function returning 1 or 0. When the current VQ index Tx,y is equal to k, φ returns 1; otherwise, φ returns 0. Generally, occurrence numbers of VQ indices in the index table are not uniform for a natural image. Figure 3 shows the distribution of occurrence numbers of VQ indices (L = 128) for image Lena, in which X axis and Y axis denote the index values and their corresponding occurrence numbers, respectively. We can observe from Figure 3 that some VQ indices occur frequently while some VQ indices are not used at all.Figure 3
Histogram of VQ index values for imageLena (L = 128).After scanning the whole index tableTe, the L different kinds of VQ indices are sorted according to their corresponding occurrence numbers γk (k = 1, 2, …, L) in the descending order. In the proposed scheme, VQ indices with higher and lower occurrence numbers are utilized to achieve additional-data embedding. Note that the distribution of VQ indices is not changed before and after VQ-encoded image encryption in our scheme. The procedure of additional-data embedding includes two stages: (1) index grouping and (2) data embedding, which are described in detail as follows.


### 3.2.1. A Index Grouping

Denote the sortedL VQ indices as c1, c2, …, cL, and their corresponding occurrence numbers are γ1, γ2, …, γL. We define the index set {cα, cα+ 1, …, cL} with lower occurrence numbers as Φ, where α is a threshold satisfying γα ≤ σ, and σ is a pre-determined parameter, which is discussed in Section 5. The relationship between α and σ can be represented as:(5)α=argminiγi≤σ.In addition to the VQ indices inΦ, the VQ indices with higher occurrence numbers are selected as another set Θ = {c1, c2, …, cβ}, and their corresponding index occurrence numbers are γ1, γ2, …, γβ, where β is set to L − α + 1. The remaining indices are formed as the set Ω = {cβ+1, cβ+2, …, cα−1}.In the following, VQ indices from the two setsΦ and Θ are exploited to construct β index groups through an iterative strategy. In detail, the β index groups are emptied initially. Then, the index with the highest occurrence number, denoted as cgj, in the current set Θ and the index with the lowest occurrence number, denoted as csj, in the current set Φ are selected to form one index group {cgj, csj}, j = 1, 2, …, β, and the two indices, cgj and csj, are removed from Θ and Φ, respectively. According to the above way, β index groups can be constructed iteratively until the two sets Θ and Φ become empty.


### 3.2.2. Data Embedding

In order to guarantee the reversibility of original VQ-encoded image on the receiver side, side information should be recorded for the indices inΦ whose occurrence numbers are not zero, i.e., ci∈Φ and γi ≠ 0, i∈ {α, α + 1, …, L}. In detail, for the jth index group {cgj, csj}, j = 1, 2, …, β, we first utilize log2(MN/n2) bits to sequentially represent the occurrence number of the index csj in Te; if the occurrence number of the index csj in Te, i.e., γi corresponding to ci∈Φ, does not equal 0, we should further utilize γi·log2(MN/n2) bits to record the position information of the γi indices in Te. Thus, the length of side information is:(6)ρ=β+∑i=αLγi⋅log2MNn2.We compress the side information by run-length coding and concatenate the compressed side information with the additional dataw to be embedded together as w′ after scrambling with the data-hiding key Kh. During data embedding, for each index group {cgj, csj}, if the occurrence number of the index csj in Te is not equal to 0, data hider should replace all the index values csj in Te with the indices cm that can be randomly selected from the set Ω, and the modified index table is denoted as Te′. Then, each VQ index in Te′ that is equal to the index cgj with higher occurrence number in one of the β index groups, i.e., {cgj, csj}, can be embedded with one binary bit. In detail, data hider scans the VQ indices in Te′ with the raster-scanning order, and if the current scanning index Tx,y is equal to cgj in the jth index group (j = 1, 2, …, β), one binary bit wi from w′ can be embedded by:(7)Tx,y′=cgj,ifwi=0,csj,ifwi=1,where Tx,y′denotes the marked VQ index. In other words, for the current scanning index Tx,y belonging to the set Θ, if the to-be-embedded bit is 0, Tx,y remains unchanged, otherwise, Tx,y is changed to its corresponding index with lower occurrence number in the same index group.After all VQ indices, belonging toΘ, in Te′ finish the above procedure, we can obtain a marked, encrypted index table Tew. Then, Tew and Ce are transmitted to the receiver for data extraction and image recovery. Note that the β index groups should also be sent to the receiver as auxiliary data ℜ.


## 3.2.1. A Index Grouping

Denote the sortedL VQ indices as c1, c2, …, cL, and their corresponding occurrence numbers are γ1, γ2, …, γL. We define the index set {cα, cα+ 1, …, cL} with lower occurrence numbers as Φ, where α is a threshold satisfying γα ≤ σ, and σ is a pre-determined parameter, which is discussed in Section 5. The relationship between α and σ can be represented as:(5)α=argminiγi≤σ.In addition to the VQ indices inΦ, the VQ indices with higher occurrence numbers are selected as another set Θ = {c1, c2, …, cβ}, and their corresponding index occurrence numbers are γ1, γ2, …, γβ, where β is set to L − α + 1. The remaining indices are formed as the set Ω = {cβ+1, cβ+2, …, cα−1}.In the following, VQ indices from the two setsΦ and Θ are exploited to construct β index groups through an iterative strategy. In detail, the β index groups are emptied initially. Then, the index with the highest occurrence number, denoted as cgj, in the current set Θ and the index with the lowest occurrence number, denoted as csj, in the current set Φ are selected to form one index group {cgj, csj}, j = 1, 2, …, β, and the two indices, cgj and csj, are removed from Θ and Φ, respectively. According to the above way, β index groups can be constructed iteratively until the two sets Θ and Φ become empty.


## 3.2.2. Data Embedding

In order to guarantee the reversibility of original VQ-encoded image on the receiver side, side information should be recorded for the indices inΦ whose occurrence numbers are not zero, i.e., ci∈Φ and γi ≠ 0, i∈ {α, α + 1, …, L}. In detail, for the jth index group {cgj, csj}, j = 1, 2, …, β, we first utilize log2(MN/n2) bits to sequentially represent the occurrence number of the index csj in Te; if the occurrence number of the index csj in Te, i.e., γi corresponding to ci∈Φ, does not equal 0, we should further utilize γi·log2(MN/n2) bits to record the position information of the γi indices in Te. Thus, the length of side information is:(6)ρ=β+∑i=αLγi⋅log2MNn2.We compress the side information by run-length coding and concatenate the compressed side information with the additional dataw to be embedded together as w′ after scrambling with the data-hiding key Kh. During data embedding, for each index group {cgj, csj}, if the occurrence number of the index csj in Te is not equal to 0, data hider should replace all the index values csj in Te with the indices cm that can be randomly selected from the set Ω, and the modified index table is denoted as Te′. Then, each VQ index in Te′ that is equal to the index cgj with higher occurrence number in one of the β index groups, i.e., {cgj, csj}, can be embedded with one binary bit. In detail, data hider scans the VQ indices in Te′ with the raster-scanning order, and if the current scanning index Tx,y is equal to cgj in the jth index group (j = 1, 2, …, β), one binary bit wi from w′ can be embedded by:(7)Tx,y′=cgj,ifwi=0,csj,ifwi=1,where Tx,y′denotes the marked VQ index. In other words, for the current scanning index Tx,y belonging to the set Θ, if the to-be-embedded bit is 0, Tx,y remains unchanged, otherwise, Tx,y is changed to its corresponding index with lower occurrence number in the same index group.After all VQ indices, belonging toΘ, in Te′ finish the above procedure, we can obtain a marked, encrypted index table Tew. Then, Tew and Ce are transmitted to the receiver for data extraction and image recovery. Note that the β index groups should also be sent to the receiver as auxiliary data ℜ.


## 3.3. Data Extraction and Image Recovery

When the receiver obtains the marked, encrypted index tableTew, the encrypted codebook Ce and the auxiliary data ℜ, data extraction and image recovery can be conducted. There are three scenarios: (1) if the receiver only has the data-hiding key Kh, the additional data w can be extracted correctly; (2) if the receiver only has the encryption key Ke, a directly decrypted index table Td, which is similar to the original index table T can be obtained; and (3) if the receiver has both Ke and Kh, additional data w and original index table T can both be recovered with no error. Details are presented as follows.


### 3.3.1. Data Extraction

First, the two index setsΘ and Φ corresponding to higher and lower occurrence numbers can be easily obtained based on the auxiliary data ℜ representing the β index groups. Then, during scanning the index table Tew in the raster-scanning order, according to the current scanning index Tx,y′ belonging to Θ or Φ, the embedded bit wi′ can be extracted sequentially, see equation (8).(8)wi′=0,ifTx,y′∈Θ,1,ifTx,y′∈Φ,no data extracted,other wise.Concatenating all extracted bitswi′, the embedded data w′ can be obtained correctly. Then, the receiver inversely scrambles w′ through the data-hiding key Kh, and parses the ρ-bits side information from w′, thus, the remaining part is the extracted additional data w.


### 3.3.2. Image Decryption

If the receiver only has the encryption keyKe = {Ke1, Ke2}, he/she can first generate the sequence of pseudo-random bits Si,j,k (i = 1, 2, …, L, j = 1, 2, …, n2, k = 1, 2, …, 8) by Ke1, which is the same with the one on the content-owner side. Through decrypting based on XOR operation, the decrypted codebook Cd can be obtained, which is exactly the same as the original codebook C.On the other hand, the receiver scans the marked, encrypted index tableTew, and if the current scanning index Tx,y′ is equal to csj in one of the β index groups (j = 1, 2, …, β), Tx,y′ is modified as the corresponding cgj in the same group. After all indices in Tew are performed, a new index table Te′ can be produced. Then, through decrypting Te′ based on permutation with Ke2, a directly decrypted index table Td, which is similar to the original index table T, can be obtained. If required, a directly decrypted image Id can also be acquired through decoding the index table Td by the VQ codebook C.As we know, the side information records the numbers and the positions for the indices inΦ with nonzero occurrence numbers, and these indices are replaced by cm randomly selected in Ω during data embedding. Therefore, due to the unavailability of the data-hiding key Kh, the side information cannot be parsed from w′, which means these recorded indices cannot be recovered from cm in Ω to csj in Φ. In other words, without Kh, Te′ cannot be recovered to Te perfectly, and Td is not exactly the same with T.


### 3.3.3. Image Recovery

If both encryption keyKe and data-hiding key Kh are available, the receiver can obtain the index table Te′ and can also parse the ρ-bits side information and the additional data w from the extracted data w′ with Kh. According to the parsed side information, the receiver can know the detailed numbers and positions for the indices in Φ with nonzero occurrence numbers, which are replaced by cm randomly selected in Ω during data embedding. Thus, through scanning the index table Te′, the indices at the positions indicated in the side information can be restored from cm to the corresponding index csj (whose occurrence number is not zero) in the index group{cgj, csj}. As a result, the index table Te′ is recovered to Te perfectly, and after decrypting Te based on permutation with Ke2, the original index table T can be recovered reversibly. As described previously, the original codebook C can be obtained through decrypting Cd with Ke1 based on XOR operation. Therefore, the additional data w, original index table T, and original codebook C can all be acquired when both Ke and Kh are available. If required, the original VQ-decoded image I can also be acquired through decoding T by C.


## 3.3.1. Data Extraction

First, the two index setsΘ and Φ corresponding to higher and lower occurrence numbers can be easily obtained based on the auxiliary data ℜ representing the β index groups. Then, during scanning the index table Tew in the raster-scanning order, according to the current scanning index Tx,y′ belonging to Θ or Φ, the embedded bit wi′ can be extracted sequentially, see equation (8).(8)wi′=0,ifTx,y′∈Θ,1,ifTx,y′∈Φ,no data extracted,other wise.Concatenating all extracted bitswi′, the embedded data w′ can be obtained correctly. Then, the receiver inversely scrambles w′ through the data-hiding key Kh, and parses the ρ-bits side information from w′, thus, the remaining part is the extracted additional data w.


## 3.3.2. Image Decryption

If the receiver only has the encryption keyKe = {Ke1, Ke2}, he/she can first generate the sequence of pseudo-random bits Si,j,k (i = 1, 2, …, L, j = 1, 2, …, n2, k = 1, 2, …, 8) by Ke1, which is the same with the one on the content-owner side. Through decrypting based on XOR operation, the decrypted codebook Cd can be obtained, which is exactly the same as the original codebook C.On the other hand, the receiver scans the marked, encrypted index tableTew, and if the current scanning index Tx,y′ is equal to csj in one of the β index groups (j = 1, 2, …, β), Tx,y′ is modified as the corresponding cgj in the same group. After all indices in Tew are performed, a new index table Te′ can be produced. Then, through decrypting Te′ based on permutation with Ke2, a directly decrypted index table Td, which is similar to the original index table T, can be obtained. If required, a directly decrypted image Id can also be acquired through decoding the index table Td by the VQ codebook C.As we know, the side information records the numbers and the positions for the indices inΦ with nonzero occurrence numbers, and these indices are replaced by cm randomly selected in Ω during data embedding. Therefore, due to the unavailability of the data-hiding key Kh, the side information cannot be parsed from w′, which means these recorded indices cannot be recovered from cm in Ω to csj in Φ. In other words, without Kh, Te′ cannot be recovered to Te perfectly, and Td is not exactly the same with T.


## 3.3.3. Image Recovery

If both encryption keyKe and data-hiding key Kh are available, the receiver can obtain the index table Te′ and can also parse the ρ-bits side information and the additional data w from the extracted data w′ with Kh. According to the parsed side information, the receiver can know the detailed numbers and positions for the indices in Φ with nonzero occurrence numbers, which are replaced by cm randomly selected in Ω during data embedding. Thus, through scanning the index table Te′, the indices at the positions indicated in the side information can be restored from cm to the corresponding index csj (whose occurrence number is not zero) in the index group{cgj, csj}. As a result, the index table Te′ is recovered to Te perfectly, and after decrypting Te based on permutation with Ke2, the original index table T can be recovered reversibly. As described previously, the original codebook C can be obtained through decrypting Cd with Ke1 based on XOR operation. Therefore, the additional data w, original index table T, and original codebook C can all be acquired when both Ke and Kh are available. If required, the original VQ-decoded image I can also be acquired through decoding T by C.


## 4. Performance Optimization

The proposed scheme described in Section3 can be considered as the baseline, which can be further optimized on the performance of hiding capacity during additional-data embedding. The optimization mainly focuses on adaptively adjusting the number of indices with lower occurrence numbers in index groups. Note that encryption operation on the content-owner side is unchanged. Details are given as follows.


### 4.1. Generalized Index Grouping

In the optimized scheme, during index grouping on the data-hider side, we define that, in each group, the number of indices with higher occurrence numbers is fixed as 1, while the number of indices with lower occurrence numbers should be 2ν – 1, where ν is a variable integer satisfying:(9)ν∈1,2,…,log2L−α+1.Thus, one indexcgj with higher occurrence numbers selected from Θ = {c1, c2, …, cβ} and 2ν – 1 indices, csj,1,csj,2,…,csj,2v−1, with lower occurrence numbers selected from Φ = {cα, cα+ 1, …, cL} can be constructed as one index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}. Note that if ν is a constant equaling 1 for all groups, the optimized scheme is just the baseline proposed in Section 3. In addition, different from the baseline scheme in Section 3, in the optimized scheme, the number β of the indices with higher occurrence numbers in Θ = {c1, c2, …, cβ} may not be equal to the number (L − α + 1) of the indices with lower occurrence numbers in Φ = {cα, cα+ 1, …, cL}.We consider the index groups including the same number 2ν – 1 of lower occurrence indices as the same (i.e., the νth) type of index groups, and a coefficient μν is defined to represent the number of index groups belonging to the νth type, ν = 1, 2, …, log2(L − α + 1). A coefficient vector μ can be given for different types of index groups, see equation (10). Table 1 lists the detailed information for different types of index groups.(10)μ=μ1,μ2,…,μlog2L−α+1.Table 1
Details of different types of existing index groups.
Group typeν = log2(L − α + 1)…ν = 2ν = 1The number ofcg in group1…11The number ofcs in group2ν – 1…22–121–1Group coefficientμν…μ2μ1Embedding ability (bits)log2(L − α + 1)…21The generalized index grouping should satisfy the following two relationships:(11)L−α+1=∑ν=1log2L−α+1μν⋅2ν−1,(12)β=∑ν=1log2L−α+1μν.Equation (11) implies that μν·(2ν – 1) represents the number of indices from Φ belonging to the νth type of index group, and in all log2(L − α + 1) types of index groups, the total number of indices from Φ should be equal to L − α + 1. On the other hand, Equation (12) guarantees that each index group has one index from Θ.For intuitive description, we present an example of generalized index grouping in Figure4. Figure 4(a) shows the sorted indices and their corresponding code words (L = 128), which are sorted in the descending order according to occurrence numbers of indices within index table Te. Here, we set the parameter σ in equation (4) to 1, thereby, α can be derived as 116. Thus, we can obtain 128 − 116 + 1 = 13 indices with lower occurrence numbers in Φ, i.e., {c116, c117, …, c128}. Then, as shown in Figure 4(b), after generalized index grouping, there are three types of index groups (including five index groups totally), corresponding to ν = 3 (μ3 = 1), ν = 2 (μ2 = 1), ν = 1 (μ1 = 3), respectively. The value of β can also be obtained as 1 + 1 + 3 = 5 through equation (12), which means that five indices with higher occurrence numbers are included in Θ, i.e., {c1, c2, …, c5}. In detail, {c1, c122, c123, c124, c125, c126, c127, c128} belongs to the third type of index group (ν = 3, μ3 = 1); {c2, c119, c120, c121} belongs to the second type of index group (ν = 2, μ2 = 1); {c3, c118}, {c4, c117}, and {c5, c116} belong to the first type of index groups (ν = 1, μ1 = 3). The coefficient vector μ is equal to [1, 1, 3]. Table 2 summarizes the index grouping information for the example in Figure 4.Figure 4
An example of generalized index grouping. (a) The sorted indices, (b) A result of index grouping.
(a)(b)Table 2
Index grouping information for the example in Figure4.
Group Typeν = 3ν = 2ν = 1The number ofcg in group111The number ofcs in group731Group coefficient113Embedding ability (bits)321


### 4.2. Multiple-Bits Embedding

Similar with the baseline scheme described in Section3, we also need to sequentially record the occurrence numbers of the indices belonging to Φ and their positions (if existing) in Te as the ρ-bits side information, see equation (6). Then, side information can be compressed through run-length coding and be concatenated with the additional data w as w′ after scrambling with the data-hiding key Kh. During data embedding, for any index in Φ whose occurrence number is not equal to 0, data hider should replace this index value in Te with the index cm that can be randomly selected from the set Ω, and the modified index table is also denoted as Te′. Then, each VQ index in Te′ that is equal to the index cgj with higher occurrence number in the generalized index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}, can be embedded with ν binary bits (j = 1, 2, …, β). In detail, data hider scans the VQ indices in Te′ with the raster-scanning order, and if the current scanning index Tx,y is equal to cgj in the jth index group, multiple bits, wi,wi+1,…,wi+v-1, from w′ can be embedded by:(13)Tx,y′=cgj,ifτi=0,csj,1,ifτi=1,⋯⋯csj,2ν−1,ifτi=2ν−1,where τi denotes the decimal value of the current ν bits wi,wi+1,…,wi+v-1 for embedding, and Tx,y′ denotes the marked VQ index embedded with the ν bits. Equation (13) means that, for the current scanning index Tx,y belonging to the set Θ, if the decimal value τi of the current to-be-embedded ν bits is 0, Tx,y remains unchanged, otherwise, Tx,y is changed to the τith corresponding index with a lower occurrence number in the same index group. After all VQ indices, belonging to Θ, in Te′ are scanned and performed with above operations orderly, the procedure of multiple-bits embedding is finished and the marked, encrypted index table Tew can be acquired.Continuing the example in Figure4, since {c1, c122, c123, c124, c125, c126, c127, c128} belongs to the third type of index group (ν = 3), three binary bits can be embedded when the current scanning index is c1; since {c2, c119, c120, c121} belongs to the second type of index group (ν = 2), two binary bits can be embedded when the current scanning index is c2; since {c3, c118}, {c4, c117} and {c5, c116} belong to the first type of index group (ν = 1), one binary bit can be embedded when the current scanning index is c3, c4, or c5. It can be inferred that, after data embedding, the occurrence numbers of c1, c2, c3, c4 and c5 in the index table are decreased because a portion of them are changed to the indices with lower occurrence number in their corresponding index groups.Obviously, if index groups are determined, the hiding capacityζ of the optimized scheme can be calculated. The occurrence numbers for the VQ indices with higher occurrence numbers, {c1, c2, …, cβ}, in Θ are denoted as f = [γ1, γ2, …, γβ]. According to the coefficient vector μ in equation (10), the occurrence number vector f can be transformed to a 1 × log2(L − α + 1) vector η = [η1, η2, …, ηlog2(L − α+ 1)]:(14)ην=0,μν=0,∑i=κν+1κν+μνγi,μν≠0,,ν=1,2,…,log2L−α+1,(15)κν=0,ν=log2L−α+1,∑j=ν+1log2L−α+1μj,ν<log2L−α+1,where ην denotes the number of indices with higher occurrence numbers belonging to the νth type of index group, ν = 1, 2, …, log2(L − α + 1). Note that, the lengths of the two vectors μ and η are equal. An example of transform procedure from f to η is given in Figure 5. Assume that the occurrence number vector is f = [1299, 964, 960, 891, 775, 755, 711] and the coefficient vector is μ = [1, 2, 3, 0, 1], respectively. With the assistance of μ, the vector η can be obtained as [711, 775 + 755, 964 + 960+891, 0, 1299] = [711, 1530, 2815, 0, 1299].Figure 5
An example of transform procedure fromf to η.Therefore, based on the above descriptions, the hiding capacityζ of the proposed scheme can be obtained as:(16)ζ=∑ν=1log2L−α+1ν⋅ην,The operations on the receiver side, including data extraction, image decryption, and recovery after receiving the marked, encrypted index tableTew, the encrypted codebook Ce , and the auxiliary data ℜ of the β index group, have minor differences with those described in Section 3. As for data extraction, Tew is first scanned in the raster-scanning order, and if the current scanning index Tx,y′ is equal to one of the indices in an index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}, j = 1, 2, …, β, ν binary bits can be extracted according to equation (13), and then, the side information and additional data can be parsed with Kh. As for image decryption, Tx,y′ is modified as corresponding to the high-occurrence index cgj in the same group, thus, Tew is changed as Te′ after all indices in Tew are scanned. Then, the original VQ codebook C and the directly decrypted index table Td are produced through decrypting Ce and Te′ with Ke1 and Ke2, respectively. The directly decrypted image Id can be obtained by decoding Td by C. As for image recovery, the index table Te′ should be first recovered to Te with the assistance of side information. As we know, side information sequentially records the occurrence numbers and the positions (if existing) for the L − α + 1 indices belonging to Φ with lower occurrence numbers in Te, among which those indices with nonzero occurrence numbers are replaced by cm randomly selected in Ω during data embedding. Therefore, with the parsed side information, the receiver can sequentially restore cm back to the corresponding index with nonzero, lower occurrence numbers in {cα, cα+ 1, …, cL}. As a result, Te′ can be recovered to Te perfectly, and after decrypting Te, original index table T can be obtained. Finally, original VQ-decoded image I can also be acquired through decoding T by C.


### 4.3. Hiding Capacity Optimization

It should be noticed that there possibly exist multiple coefficient vectorsμ that can satisfy the two relationships in equations (11) and (12), and different coefficient vectors μ may lead to different hiding capacities. Therefore, by finding the optimal coefficient vector, hiding capacity of the proposed scheme can be further optimized.Suppose that there areλ different coefficient vectors, μ(1), μ(2), …, μ(λ), satisfying equations (11) and (12), which can be represented by a matrix U sized λ × log2(L − α + 1):(17)U=μ1μ2⋮μλ=μ11μ21⋯μlog2L−α+11μ12μ22⋯μlog2L−α+12⋮⋮⋯⋮μ1λμ2λ⋯μlog2L−α+1λ,where μ(i) = [μ1i,μ2i,…,μlog2L−α+1i], i = 1, 2, …, λ. According to equations (14) and (15), we can know that each row in the matrix U, i.e., μ(i), corresponds to a vector η(i) based on the occurrence number vector f = [γ1, γ2, …, γβ]. Thus, the λ vectors, η(1), η(2), …, η(λ), can form a matrix Γ that has the same size with U:(18)Γ=η1η2⋮ηλ=η11η21⋯ηlog2L−α+11η12η22⋯ηlog2L−α+12⋮⋮⋯⋮η1λη2λ⋯ηlog2L−α+1λ,where η(i) = [η1i,η2i,…,ηlog2L−α+1i], i = 1, 2, …, λ. Then, based on equation (16), we can obtain λ values, ζ(1), ζ(2), …, ζ(λ), of the hiding capacity:(19)ζi=r⋅ηiT,where r denotes the row vector [1, 2, …, log2(L − α + 1)], and ζ(i) is the hiding capacity corresponding to the coefficient vector μ(i) for index groups, i = 1, 2, …, λ. With equation (20), the optimal coefficient vector can be found as μ(i∗) by dynamic programming, which means that the optimal result of generalized index grouping is determined. Finally, the largest hiding capacity of the proposed scheme after optimization can be acquired as ζ(i∗).(20)i∗=argmaxiζi,subject toi∈1,2,…,λ.


## 4.1. Generalized Index Grouping

In the optimized scheme, during index grouping on the data-hider side, we define that, in each group, the number of indices with higher occurrence numbers is fixed as 1, while the number of indices with lower occurrence numbers should be 2ν – 1, where ν is a variable integer satisfying:(9)ν∈1,2,…,log2L−α+1.Thus, one indexcgj with higher occurrence numbers selected from Θ = {c1, c2, …, cβ} and 2ν – 1 indices, csj,1,csj,2,…,csj,2v−1, with lower occurrence numbers selected from Φ = {cα, cα+ 1, …, cL} can be constructed as one index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}. Note that if ν is a constant equaling 1 for all groups, the optimized scheme is just the baseline proposed in Section 3. In addition, different from the baseline scheme in Section 3, in the optimized scheme, the number β of the indices with higher occurrence numbers in Θ = {c1, c2, …, cβ} may not be equal to the number (L − α + 1) of the indices with lower occurrence numbers in Φ = {cα, cα+ 1, …, cL}.We consider the index groups including the same number 2ν – 1 of lower occurrence indices as the same (i.e., the νth) type of index groups, and a coefficient μν is defined to represent the number of index groups belonging to the νth type, ν = 1, 2, …, log2(L − α + 1). A coefficient vector μ can be given for different types of index groups, see equation (10). Table 1 lists the detailed information for different types of index groups.(10)μ=μ1,μ2,…,μlog2L−α+1.Table 1
Details of different types of existing index groups.
Group typeν = log2(L − α + 1)…ν = 2ν = 1The number ofcg in group1…11The number ofcs in group2ν – 1…22–121–1Group coefficientμν…μ2μ1Embedding ability (bits)log2(L − α + 1)…21The generalized index grouping should satisfy the following two relationships:(11)L−α+1=∑ν=1log2L−α+1μν⋅2ν−1,(12)β=∑ν=1log2L−α+1μν.Equation (11) implies that μν·(2ν – 1) represents the number of indices from Φ belonging to the νth type of index group, and in all log2(L − α + 1) types of index groups, the total number of indices from Φ should be equal to L − α + 1. On the other hand, Equation (12) guarantees that each index group has one index from Θ.For intuitive description, we present an example of generalized index grouping in Figure4. Figure 4(a) shows the sorted indices and their corresponding code words (L = 128), which are sorted in the descending order according to occurrence numbers of indices within index table Te. Here, we set the parameter σ in equation (4) to 1, thereby, α can be derived as 116. Thus, we can obtain 128 − 116 + 1 = 13 indices with lower occurrence numbers in Φ, i.e., {c116, c117, …, c128}. Then, as shown in Figure 4(b), after generalized index grouping, there are three types of index groups (including five index groups totally), corresponding to ν = 3 (μ3 = 1), ν = 2 (μ2 = 1), ν = 1 (μ1 = 3), respectively. The value of β can also be obtained as 1 + 1 + 3 = 5 through equation (12), which means that five indices with higher occurrence numbers are included in Θ, i.e., {c1, c2, …, c5}. In detail, {c1, c122, c123, c124, c125, c126, c127, c128} belongs to the third type of index group (ν = 3, μ3 = 1); {c2, c119, c120, c121} belongs to the second type of index group (ν = 2, μ2 = 1); {c3, c118}, {c4, c117}, and {c5, c116} belong to the first type of index groups (ν = 1, μ1 = 3). The coefficient vector μ is equal to [1, 1, 3]. Table 2 summarizes the index grouping information for the example in Figure 4.Figure 4
An example of generalized index grouping. (a) The sorted indices, (b) A result of index grouping.
(a)(b)Table 2
Index grouping information for the example in Figure4.
Group Typeν = 3ν = 2ν = 1The number ofcg in group111The number ofcs in group731Group coefficient113Embedding ability (bits)321


## 4.2. Multiple-Bits Embedding

Similar with the baseline scheme described in Section3, we also need to sequentially record the occurrence numbers of the indices belonging to Φ and their positions (if existing) in Te as the ρ-bits side information, see equation (6). Then, side information can be compressed through run-length coding and be concatenated with the additional data w as w′ after scrambling with the data-hiding key Kh. During data embedding, for any index in Φ whose occurrence number is not equal to 0, data hider should replace this index value in Te with the index cm that can be randomly selected from the set Ω, and the modified index table is also denoted as Te′. Then, each VQ index in Te′ that is equal to the index cgj with higher occurrence number in the generalized index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}, can be embedded with ν binary bits (j = 1, 2, …, β). In detail, data hider scans the VQ indices in Te′ with the raster-scanning order, and if the current scanning index Tx,y is equal to cgj in the jth index group, multiple bits, wi,wi+1,…,wi+v-1, from w′ can be embedded by:(13)Tx,y′=cgj,ifτi=0,csj,1,ifτi=1,⋯⋯csj,2ν−1,ifτi=2ν−1,where τi denotes the decimal value of the current ν bits wi,wi+1,…,wi+v-1 for embedding, and Tx,y′ denotes the marked VQ index embedded with the ν bits. Equation (13) means that, for the current scanning index Tx,y belonging to the set Θ, if the decimal value τi of the current to-be-embedded ν bits is 0, Tx,y remains unchanged, otherwise, Tx,y is changed to the τith corresponding index with a lower occurrence number in the same index group. After all VQ indices, belonging to Θ, in Te′ are scanned and performed with above operations orderly, the procedure of multiple-bits embedding is finished and the marked, encrypted index table Tew can be acquired.Continuing the example in Figure4, since {c1, c122, c123, c124, c125, c126, c127, c128} belongs to the third type of index group (ν = 3), three binary bits can be embedded when the current scanning index is c1; since {c2, c119, c120, c121} belongs to the second type of index group (ν = 2), two binary bits can be embedded when the current scanning index is c2; since {c3, c118}, {c4, c117} and {c5, c116} belong to the first type of index group (ν = 1), one binary bit can be embedded when the current scanning index is c3, c4, or c5. It can be inferred that, after data embedding, the occurrence numbers of c1, c2, c3, c4 and c5 in the index table are decreased because a portion of them are changed to the indices with lower occurrence number in their corresponding index groups.Obviously, if index groups are determined, the hiding capacityζ of the optimized scheme can be calculated. The occurrence numbers for the VQ indices with higher occurrence numbers, {c1, c2, …, cβ}, in Θ are denoted as f = [γ1, γ2, …, γβ]. According to the coefficient vector μ in equation (10), the occurrence number vector f can be transformed to a 1 × log2(L − α + 1) vector η = [η1, η2, …, ηlog2(L − α+ 1)]:(14)ην=0,μν=0,∑i=κν+1κν+μνγi,μν≠0,,ν=1,2,…,log2L−α+1,(15)κν=0,ν=log2L−α+1,∑j=ν+1log2L−α+1μj,ν<log2L−α+1,where ην denotes the number of indices with higher occurrence numbers belonging to the νth type of index group, ν = 1, 2, …, log2(L − α + 1). Note that, the lengths of the two vectors μ and η are equal. An example of transform procedure from f to η is given in Figure 5. Assume that the occurrence number vector is f = [1299, 964, 960, 891, 775, 755, 711] and the coefficient vector is μ = [1, 2, 3, 0, 1], respectively. With the assistance of μ, the vector η can be obtained as [711, 775 + 755, 964 + 960+891, 0, 1299] = [711, 1530, 2815, 0, 1299].Figure 5
An example of transform procedure fromf to η.Therefore, based on the above descriptions, the hiding capacityζ of the proposed scheme can be obtained as:(16)ζ=∑ν=1log2L−α+1ν⋅ην,The operations on the receiver side, including data extraction, image decryption, and recovery after receiving the marked, encrypted index tableTew, the encrypted codebook Ce , and the auxiliary data ℜ of the β index group, have minor differences with those described in Section 3. As for data extraction, Tew is first scanned in the raster-scanning order, and if the current scanning index Tx,y′ is equal to one of the indices in an index group, i.e., {cgj, csj,1,csj,2,…,csj,2v−1)}, j = 1, 2, …, β, ν binary bits can be extracted according to equation (13), and then, the side information and additional data can be parsed with Kh. As for image decryption, Tx,y′ is modified as corresponding to the high-occurrence index cgj in the same group, thus, Tew is changed as Te′ after all indices in Tew are scanned. Then, the original VQ codebook C and the directly decrypted index table Td are produced through decrypting Ce and Te′ with Ke1 and Ke2, respectively. The directly decrypted image Id can be obtained by decoding Td by C. As for image recovery, the index table Te′ should be first recovered to Te with the assistance of side information. As we know, side information sequentially records the occurrence numbers and the positions (if existing) for the L − α + 1 indices belonging to Φ with lower occurrence numbers in Te, among which those indices with nonzero occurrence numbers are replaced by cm randomly selected in Ω during data embedding. Therefore, with the parsed side information, the receiver can sequentially restore cm back to the corresponding index with nonzero, lower occurrence numbers in {cα, cα+ 1, …, cL}. As a result, Te′ can be recovered to Te perfectly, and after decrypting Te, original index table T can be obtained. Finally, original VQ-decoded image I can also be acquired through decoding T by C.


## 4.3. Hiding Capacity Optimization

It should be noticed that there possibly exist multiple coefficient vectorsμ that can satisfy the two relationships in equations (11) and (12), and different coefficient vectors μ may lead to different hiding capacities. Therefore, by finding the optimal coefficient vector, hiding capacity of the proposed scheme can be further optimized.Suppose that there areλ different coefficient vectors, μ(1), μ(2), …, μ(λ), satisfying equations (11) and (12), which can be represented by a matrix U sized λ × log2(L − α + 1):(17)U=μ1μ2⋮μλ=μ11μ21⋯μlog2L−α+11μ12μ22⋯μlog2L−α+12⋮⋮⋯⋮μ1λμ2λ⋯μlog2L−α+1λ,where μ(i) = [μ1i,μ2i,…,μlog2L−α+1i], i = 1, 2, …, λ. According to equations (14) and (15), we can know that each row in the matrix U, i.e., μ(i), corresponds to a vector η(i) based on the occurrence number vector f = [γ1, γ2, …, γβ]. Thus, the λ vectors, η(1), η(2), …, η(λ), can form a matrix Γ that has the same size with U:(18)Γ=η1η2⋮ηλ=η11η21⋯ηlog2L−α+11η12η22⋯ηlog2L−α+12⋮⋮⋯⋮η1λη2λ⋯ηlog2L−α+1λ,where η(i) = [η1i,η2i,…,ηlog2L−α+1i], i = 1, 2, …, λ. Then, based on equation (16), we can obtain λ values, ζ(1), ζ(2), …, ζ(λ), of the hiding capacity:(19)ζi=r⋅ηiT,where r denotes the row vector [1, 2, …, log2(L − α + 1)], and ζ(i) is the hiding capacity corresponding to the coefficient vector μ(i) for index groups, i = 1, 2, …, λ. With equation (20), the optimal coefficient vector can be found as μ(i∗) by dynamic programming, which means that the optimal result of generalized index grouping is determined. Finally, the largest hiding capacity of the proposed scheme after optimization can be acquired as ζ(i∗).(20)i∗=argmaxiζi,subject toi∈1,2,…,λ.


## 5. Experimental Results and Analysis

In order to demonstrate the effectiveness and superiority of our scheme, experiments were conducted on a large number of VQ-encoded images, and the environment of our experiments was based on a personal computer with a 3.20 GHz Intel i5 processor, 4.00 GB memory, Windows 10 operating system, and Matlab R2016a. In the following, results of the proposed scheme, including the reversibility, hiding capacityζ , and visual quality of directly decrypted image Id, are first given. Then, the influences of parameter σ on the performances are analyzed. Finally, comparisons with state-of-the-art schemes are discussed.


### 5.1. Results of the Proposed Scheme

#### 5.1.1. Reversibility

Figure6(a) shows an original VQ-decoded image I for Lena sized 512 × 512, the length L of corresponding VQ codebook C is 256. In this experiment, the parameter σ in equation (6) was set as 1, and α was equal to 226 accordingly. The VQ-decoded, encrypted image with index permutation and codebook encryption is shown in Figure 6(b), which is the result through decoding Te with Ce. It can be observed that the contents of the original VQ-decoded image I are effectively masked after encryption. Figure 6(c) shows the VQ decoded, encrypted image after data embedding, which is the result through decoding Tew with Ce. The hiding capacity ζ was 12954 bits. Figure 6(d) is the directly decrypted image Id for Figure 6(c), which is the result through decoding Td with C. PSNR of the directly decrypted result Id in Figure 6(d) is 41.80 dB with respect to the original VQ-decoded image I in Figure 6(a). Recovered image, i.e., the result through decoding T with C, is exactly the same as I, i.e., PSNR = +∞, which demonstrates the reversibility of our scheme.Figure 6
Results of the proposed scheme for imageLena. (a) Original VQ-image with decoding (T) by C. (b) Encrypted VQ-image with decoding Te by Ce. (c) Marked, encrypted VQ-image with decoding Tew by Ce (ζ = 12954 bits). (d) Directly decrypted VQ-image with decoding Td by (C) (PSNR = 41.80 dB).
(a)(b)(c)(d)


#### 5.1.2. Hiding Capacity

Figure7 shows four standard test images sized 512 × 512, including Airplane, Baboon, Lena, and Peppers. VQ compression was conducted for these four images, and the sizes L of the adopted codebooks can be 128, 256, 512, and 1024. Figure 8 shows hiding capacities ζ of our scheme for the four VQ-encoded images after encryption (σ = 1), in which (a)–(d) corresponds to the VQ codebook sizes L = 128, 256, 512, and 1024, respectively. Note that the abscissa denotes the different coefficient vectors μ and the ordinate denotes corresponding hiding capacities ζ (bits). It can be observed that the codebook with larger size L can generally obtain greater hiding capacity ζ than the codebook with smaller size, since a large-size codebook can lead to more index groups for data embedding based on more VQ indices with lower occurrence numbers.Figure 7
Four standard test images. (a) Airplane. (b) Baboon. (c) Lena. (d) Peppers.
(a)(b)(c)(d)Figure 8
Hiding capacities with respect to different coefficient vectorsμ under four kinds of codebook sizes L (σ = 1). (a) L = 128. (b) L = 256. (c) L = 512. (d) L = 1024.
(a)(b)(c)(d)Besides the four images in Figure7, Table 3 lists the largest hiding capacities with the optimal coefficient vectors μ(i∗) of our scheme for more images. Actually, for different images, the hiding capacity of our scheme is mainly related with two aspects: (1) the value of (L − α + (1) under a given parameter σ, i.e., the number of the low-occurrence indices {cα, cα+ 1, …, cL} and (2) the occurrence number vector f = [γ1, γ2, …, γβ], i.e., occurrence numbers of high-occurrence indices {c1, c2, …, cβ} in Te, see equations (14)–(16). Figure 9 shows the histograms of VQ indices that are sorted in the descending order according to occurrence numbers for the two images Airplane and Baboon (L = 512). We can clearly observe that the index histogram distribution of Airplane is more concentrated than that of Baboon, which means that the number of low-occurrence indices {cα, cα+ 1, …, cL} and the occurrence numbers of high-occurrence indices {c1, c2, …, cβ} for Airplane are greater than those of Baboon. Correspondingly, it can be found from Table 3 that the hiding capacity for Airplane is significantly greater than that of Baboon. In addition, we also conducted experiments on the UCID image database [45], which consists of 1338 distinct images with the sizes of 512 × 384 and 384 × 512, see the last row of Table 3. For color images in the UCID database, the luminance components were applied for test, and the average hiding capacities are 6328 bits, 14649 bits, 21819 bits, and 29643 bits, when L is equal to 128, 256, 512, and 1024, respectively.Table 3
The largest hiding capacities with the optimal coefficient vectors andσ = 1 (bits).
ImagesL = 128L = 256L = 512L = 1024Aerial4902180042498432209Baboon6835736075718800Barbara3324104391256616765Crowd7614215582435931859Peppers4738189902428732834Airplane13855268763442445128Lena4889129541762423171UCID6328146492181929643Figure 9
Histograms of sorted VQ indices (L = 512). (a) Airplane, (b) Baboon.
(a)(b)


#### 5.1.3. Visual Quality of Directly-Decrypted Image

As described previously, on the receiver side, the marked, encrypted index tableTew, is scanned in raster-scanning order, and if the current scanning index Tx,y′ is equal to one of low-occurrence indices in an index group, i.e., {csj,1,csj,2,…,csj,2v−1}, is equal to one of low-occurrence is modified as the corresponding the high-occurrence index cgj in the same group, j = 1, 2, …, β. After all indices in Tew are performed, Tew is changed as Te′. Then, after decrypting Te′, a directly-decrypted index table Td is generated, and the directly-decrypted image Id is obtained with decoding Td by VQ codebook C.Visual quality of directly-decrypted imageId for the proposed scheme is given in Table 4. As it reveals, PSNR values of directly-decrypted images decrease when the size L of VQ codebook increases. When the codebook size L increases, there may appear more VQ indices whose occurrence numbers are low (≤ σ) but non-zeros in the index table Te. These indices should be replaced with the index cm randomly selected from the set Ω before data embedding, however, these indices cannot be recovered during image decryption, which causes the distortions in the directly-decrypted image Id with respect to the original VQ-decoded image I. That is to say, larger codebook size L leads to more indices with non-zero, lower occurrence numbers that cannot be recovered after image decryption, thereby, lower PSNR of Id.Table 4
PSNR of directly-decrypted imageId (dB).
ImagesL = 128L = 256L = 512L = 1024Aerial45.2038.1032.0028.10Baboon50.4042.8039.5037.00Barbara45.9045.0038.5035.40Crowd62.6043.1038.4033.00Peppers53.6042.7038.2033.20Airplane43.9040.3036.8030.50Lena49.1041.8038.6031.60UCID44.9140.7335.3630.13


### 5.2. Performance Influence of Parameterσ

The parameterσ in equation (6) determines how many indices with lower occurrence numbers can be utilized in index grouping and data embedding; hence, the parameter σ affects the performance of hiding capacity and PSNR for the directly decrypted image, which are demonstrated in Figures 10 and 11, respectively. We can find that, with the increase of σ, the hiding capacity of our scheme increases, while the PSNR of directly decrypted image decreases. Because larger σ involves more indices with lower occurrence numbers for index grouping and data embedding, the hiding capability becomes greater with the increase of parameter σ, see Figure 10. On the other hand, when σ is equal to 0, the occurrence numbers of the L − α + 1 indices {cα, cα+ 1, …, cL} are all zeros and no indices are required to be changed as cm before data embedding; thus, after image decryption, original index table T can be obtained since Te′ is equal to Te, and the directly decrypted image Id is exactly the same as I, i.e., PSNR = inf. However, with the increase of σ, the value of α decreases, and more indices with nonzero occurrence numbers may be included in Φ, which are required to be changed as cm before data embedding and cannot be recovered after image decryption, thereby, leading to lower PSNR of directly decrypted image Id, see Figure 11.Figure 10
Hiding capacity under different values of parameterσ (bits). (a) L = 128. (b) L = 256. (c) L = 512.
(a)(b)(c)Figure 11
PSNR of directly decrypted image (I)d under different values of parameter σ (dB). (a) L = 128. (b) L = 256. (c) L = 512.
(a)(b)(c)


### 5.3. Comparison with State-of-the-Art Schemes

Since there are few RDHEI schemes for VQ-encoded images, we chose the other five typical RDHEI schemes, i.e., Zhang’s scheme [22], Qian and Zhang’s scheme [26], Yin et al.’s scheme [40], Qian et al.’s scheme [41], and Wu et al.’s scheme [42], for comparing the performance of embedding rate. In detail, the RDHEI schemes [22, 26] focused on uncompressed gray scale images, the schemes [40, 41] were designed for JPEG-encoded images, and the scheme [42] was applied in palette color images. As for the proposed scheme, we utilized four kinds of VQ codebooks with sizes of 128, 256, 512, and 1024, and the parameter σ was set to 0 and 1. It was worth noting that we used the unit of bpi (bits per index) to represent the embedding rate for our RDHEI scheme of VQ-encoded images and the unit of bpp (bits per pixel) for other schemes. Comparison results for the four standard images are given in Table 5. It can be observed from the results that our scheme generally has a competitive performance of embedding rate compared with the schemes in Refs. [22, 26, 40–42].Table 5
Comparisons of embedding rate between the proposed scheme with Refs. [22, 26, 40–42].
SchemesAirplaneBaboonLenaPeppersZhang’s scheme [22]0.05000.05000.05000.0500Qian and Zhang’s scheme [26]0.29520.29520.29520.2952Yin et al.’s scheme [40]0.16470.87670.29190.3060Qian et al.’s scheme [41]0.05650.11510.05590.0649Wu et al.’s scheme [42]0.05550.57300.02040.3420Proposed scheme (L = 128, σ = 0)0.60910.37130.13810.2388Proposed scheme (L = 128, σ = 1)0.84560.41710.29840.2891Proposed scheme (L = 256, σ = 0)1.39190.35360.59090.7957Proposed scheme (L = 256, σ = 1)1.64030.44920.79061.1590Proposed scheme (L = 512, σ = 0)1.82270.37100.80481.1459Proposed scheme (L = 512, σ = 1)2.10100.46201.07561.4823Proposed scheme (L = 1024, σ = 0)2.42250.43581.10241.6953Proposed scheme (L = 1024, σ = 1)2.75440.53711.41422.0040


## 5.1. Results of the Proposed Scheme

### 5.1.1. Reversibility

Figure6(a) shows an original VQ-decoded image I for Lena sized 512 × 512, the length L of corresponding VQ codebook C is 256. In this experiment, the parameter σ in equation (6) was set as 1, and α was equal to 226 accordingly. The VQ-decoded, encrypted image with index permutation and codebook encryption is shown in Figure 6(b), which is the result through decoding Te with Ce. It can be observed that the contents of the original VQ-decoded image I are effectively masked after encryption. Figure 6(c) shows the VQ decoded, encrypted image after data embedding, which is the result through decoding Tew with Ce. The hiding capacity ζ was 12954 bits. Figure 6(d) is the directly decrypted image Id for Figure 6(c), which is the result through decoding Td with C. PSNR of the directly decrypted result Id in Figure 6(d) is 41.80 dB with respect to the original VQ-decoded image I in Figure 6(a). Recovered image, i.e., the result through decoding T with C, is exactly the same as I, i.e., PSNR = +∞, which demonstrates the reversibility of our scheme.Figure 6
Results of the proposed scheme for imageLena. (a) Original VQ-image with decoding (T) by C. (b) Encrypted VQ-image with decoding Te by Ce. (c) Marked, encrypted VQ-image with decoding Tew by Ce (ζ = 12954 bits). (d) Directly decrypted VQ-image with decoding Td by (C) (PSNR = 41.80 dB).
(a)(b)(c)(d)


### 5.1.2. Hiding Capacity

Figure7 shows four standard test images sized 512 × 512, including Airplane, Baboon, Lena, and Peppers. VQ compression was conducted for these four images, and the sizes L of the adopted codebooks can be 128, 256, 512, and 1024. Figure 8 shows hiding capacities ζ of our scheme for the four VQ-encoded images after encryption (σ = 1), in which (a)–(d) corresponds to the VQ codebook sizes L = 128, 256, 512, and 1024, respectively. Note that the abscissa denotes the different coefficient vectors μ and the ordinate denotes corresponding hiding capacities ζ (bits). It can be observed that the codebook with larger size L can generally obtain greater hiding capacity ζ than the codebook with smaller size, since a large-size codebook can lead to more index groups for data embedding based on more VQ indices with lower occurrence numbers.Figure 7
Four standard test images. (a) Airplane. (b) Baboon. (c) Lena. (d) Peppers.
(a)(b)(c)(d)Figure 8
Hiding capacities with respect to different coefficient vectorsμ under four kinds of codebook sizes L (σ = 1). (a) L = 128. (b) L = 256. (c) L = 512. (d) L = 1024.
(a)(b)(c)(d)Besides the four images in Figure7, Table 3 lists the largest hiding capacities with the optimal coefficient vectors μ(i∗) of our scheme for more images. Actually, for different images, the hiding capacity of our scheme is mainly related with two aspects: (1) the value of (L − α + (1) under a given parameter σ, i.e., the number of the low-occurrence indices {cα, cα+ 1, …, cL} and (2) the occurrence number vector f = [γ1, γ2, …, γβ], i.e., occurrence numbers of high-occurrence indices {c1, c2, …, cβ} in Te, see equations (14)–(16). Figure 9 shows the histograms of VQ indices that are sorted in the descending order according to occurrence numbers for the two images Airplane and Baboon (L = 512). We can clearly observe that the index histogram distribution of Airplane is more concentrated than that of Baboon, which means that the number of low-occurrence indices {cα, cα+ 1, …, cL} and the occurrence numbers of high-occurrence indices {c1, c2, …, cβ} for Airplane are greater than those of Baboon. Correspondingly, it can be found from Table 3 that the hiding capacity for Airplane is significantly greater than that of Baboon. In addition, we also conducted experiments on the UCID image database [45], which consists of 1338 distinct images with the sizes of 512 × 384 and 384 × 512, see the last row of Table 3. For color images in the UCID database, the luminance components were applied for test, and the average hiding capacities are 6328 bits, 14649 bits, 21819 bits, and 29643 bits, when L is equal to 128, 256, 512, and 1024, respectively.Table 3
The largest hiding capacities with the optimal coefficient vectors andσ = 1 (bits).
ImagesL = 128L = 256L = 512L = 1024Aerial4902180042498432209Baboon6835736075718800Barbara3324104391256616765Crowd7614215582435931859Peppers4738189902428732834Airplane13855268763442445128Lena4889129541762423171UCID6328146492181929643Figure 9
Histograms of sorted VQ indices (L = 512). (a) Airplane, (b) Baboon.
(a)(b)


### 5.1.3. Visual Quality of Directly-Decrypted Image

As described previously, on the receiver side, the marked, encrypted index tableTew, is scanned in raster-scanning order, and if the current scanning index Tx,y′ is equal to one of low-occurrence indices in an index group, i.e., {csj,1,csj,2,…,csj,2v−1}, is equal to one of low-occurrence is modified as the corresponding the high-occurrence index cgj in the same group, j = 1, 2, …, β. After all indices in Tew are performed, Tew is changed as Te′. Then, after decrypting Te′, a directly-decrypted index table Td is generated, and the directly-decrypted image Id is obtained with decoding Td by VQ codebook C.Visual quality of directly-decrypted imageId for the proposed scheme is given in Table 4. As it reveals, PSNR values of directly-decrypted images decrease when the size L of VQ codebook increases. When the codebook size L increases, there may appear more VQ indices whose occurrence numbers are low (≤ σ) but non-zeros in the index table Te. These indices should be replaced with the index cm randomly selected from the set Ω before data embedding, however, these indices cannot be recovered during image decryption, which causes the distortions in the directly-decrypted image Id with respect to the original VQ-decoded image I. That is to say, larger codebook size L leads to more indices with non-zero, lower occurrence numbers that cannot be recovered after image decryption, thereby, lower PSNR of Id.Table 4
PSNR of directly-decrypted imageId (dB).
ImagesL = 128L = 256L = 512L = 1024Aerial45.2038.1032.0028.10Baboon50.4042.8039.5037.00Barbara45.9045.0038.5035.40Crowd62.6043.1038.4033.00Peppers53.6042.7038.2033.20Airplane43.9040.3036.8030.50Lena49.1041.8038.6031.60UCID44.9140.7335.3630.13


## 5.1.1. Reversibility

Figure6(a) shows an original VQ-decoded image I for Lena sized 512 × 512, the length L of corresponding VQ codebook C is 256. In this experiment, the parameter σ in equation (6) was set as 1, and α was equal to 226 accordingly. The VQ-decoded, encrypted image with index permutation and codebook encryption is shown in Figure 6(b), which is the result through decoding Te with Ce. It can be observed that the contents of the original VQ-decoded image I are effectively masked after encryption. Figure 6(c) shows the VQ decoded, encrypted image after data embedding, which is the result through decoding Tew with Ce. The hiding capacity ζ was 12954 bits. Figure 6(d) is the directly decrypted image Id for Figure 6(c), which is the result through decoding Td with C. PSNR of the directly decrypted result Id in Figure 6(d) is 41.80 dB with respect to the original VQ-decoded image I in Figure 6(a). Recovered image, i.e., the result through decoding T with C, is exactly the same as I, i.e., PSNR = +∞, which demonstrates the reversibility of our scheme.Figure 6
Results of the proposed scheme for imageLena. (a) Original VQ-image with decoding (T) by C. (b) Encrypted VQ-image with decoding Te by Ce. (c) Marked, encrypted VQ-image with decoding Tew by Ce (ζ = 12954 bits). (d) Directly decrypted VQ-image with decoding Td by (C) (PSNR = 41.80 dB).
(a)(b)(c)(d)


## 5.1.2. Hiding Capacity

Figure7 shows four standard test images sized 512 × 512, including Airplane, Baboon, Lena, and Peppers. VQ compression was conducted for these four images, and the sizes L of the adopted codebooks can be 128, 256, 512, and 1024. Figure 8 shows hiding capacities ζ of our scheme for the four VQ-encoded images after encryption (σ = 1), in which (a)–(d) corresponds to the VQ codebook sizes L = 128, 256, 512, and 1024, respectively. Note that the abscissa denotes the different coefficient vectors μ and the ordinate denotes corresponding hiding capacities ζ (bits). It can be observed that the codebook with larger size L can generally obtain greater hiding capacity ζ than the codebook with smaller size, since a large-size codebook can lead to more index groups for data embedding based on more VQ indices with lower occurrence numbers.Figure 7
Four standard test images. (a) Airplane. (b) Baboon. (c) Lena. (d) Peppers.
(a)(b)(c)(d)Figure 8
Hiding capacities with respect to different coefficient vectorsμ under four kinds of codebook sizes L (σ = 1). (a) L = 128. (b) L = 256. (c) L = 512. (d) L = 1024.
(a)(b)(c)(d)Besides the four images in Figure7, Table 3 lists the largest hiding capacities with the optimal coefficient vectors μ(i∗) of our scheme for more images. Actually, for different images, the hiding capacity of our scheme is mainly related with two aspects: (1) the value of (L − α + (1) under a given parameter σ, i.e., the number of the low-occurrence indices {cα, cα+ 1, …, cL} and (2) the occurrence number vector f = [γ1, γ2, …, γβ], i.e., occurrence numbers of high-occurrence indices {c1, c2, …, cβ} in Te, see equations (14)–(16). Figure 9 shows the histograms of VQ indices that are sorted in the descending order according to occurrence numbers for the two images Airplane and Baboon (L = 512). We can clearly observe that the index histogram distribution of Airplane is more concentrated than that of Baboon, which means that the number of low-occurrence indices {cα, cα+ 1, …, cL} and the occurrence numbers of high-occurrence indices {c1, c2, …, cβ} for Airplane are greater than those of Baboon. Correspondingly, it can be found from Table 3 that the hiding capacity for Airplane is significantly greater than that of Baboon. In addition, we also conducted experiments on the UCID image database [45], which consists of 1338 distinct images with the sizes of 512 × 384 and 384 × 512, see the last row of Table 3. For color images in the UCID database, the luminance components were applied for test, and the average hiding capacities are 6328 bits, 14649 bits, 21819 bits, and 29643 bits, when L is equal to 128, 256, 512, and 1024, respectively.Table 3
The largest hiding capacities with the optimal coefficient vectors andσ = 1 (bits).
ImagesL = 128L = 256L = 512L = 1024Aerial4902180042498432209Baboon6835736075718800Barbara3324104391256616765Crowd7614215582435931859Peppers4738189902428732834Airplane13855268763442445128Lena4889129541762423171UCID6328146492181929643Figure 9
Histograms of sorted VQ indices (L = 512). (a) Airplane, (b) Baboon.
(a)(b)


## 5.1.3. Visual Quality of Directly-Decrypted Image

As described previously, on the receiver side, the marked, encrypted index tableTew, is scanned in raster-scanning order, and if the current scanning index Tx,y′ is equal to one of low-occurrence indices in an index group, i.e., {csj,1,csj,2,…,csj,2v−1}, is equal to one of low-occurrence is modified as the corresponding the high-occurrence index cgj in the same group, j = 1, 2, …, β. After all indices in Tew are performed, Tew is changed as Te′. Then, after decrypting Te′, a directly-decrypted index table Td is generated, and the directly-decrypted image Id is obtained with decoding Td by VQ codebook C.Visual quality of directly-decrypted imageId for the proposed scheme is given in Table 4. As it reveals, PSNR values of directly-decrypted images decrease when the size L of VQ codebook increases. When the codebook size L increases, there may appear more VQ indices whose occurrence numbers are low (≤ σ) but non-zeros in the index table Te. These indices should be replaced with the index cm randomly selected from the set Ω before data embedding, however, these indices cannot be recovered during image decryption, which causes the distortions in the directly-decrypted image Id with respect to the original VQ-decoded image I. That is to say, larger codebook size L leads to more indices with non-zero, lower occurrence numbers that cannot be recovered after image decryption, thereby, lower PSNR of Id.Table 4
PSNR of directly-decrypted imageId (dB).
ImagesL = 128L = 256L = 512L = 1024Aerial45.2038.1032.0028.10Baboon50.4042.8039.5037.00Barbara45.9045.0038.5035.40Crowd62.6043.1038.4033.00Peppers53.6042.7038.2033.20Airplane43.9040.3036.8030.50Lena49.1041.8038.6031.60UCID44.9140.7335.3630.13


## 5.2. Performance Influence of Parameterσ

The parameterσ in equation (6) determines how many indices with lower occurrence numbers can be utilized in index grouping and data embedding; hence, the parameter σ affects the performance of hiding capacity and PSNR for the directly decrypted image, which are demonstrated in Figures 10 and 11, respectively. We can find that, with the increase of σ, the hiding capacity of our scheme increases, while the PSNR of directly decrypted image decreases. Because larger σ involves more indices with lower occurrence numbers for index grouping and data embedding, the hiding capability becomes greater with the increase of parameter σ, see Figure 10. On the other hand, when σ is equal to 0, the occurrence numbers of the L − α + 1 indices {cα, cα+ 1, …, cL} are all zeros and no indices are required to be changed as cm before data embedding; thus, after image decryption, original index table T can be obtained since Te′ is equal to Te, and the directly decrypted image Id is exactly the same as I, i.e., PSNR = inf. However, with the increase of σ, the value of α decreases, and more indices with nonzero occurrence numbers may be included in Φ, which are required to be changed as cm before data embedding and cannot be recovered after image decryption, thereby, leading to lower PSNR of directly decrypted image Id, see Figure 11.Figure 10
Hiding capacity under different values of parameterσ (bits). (a) L = 128. (b) L = 256. (c) L = 512.
(a)(b)(c)Figure 11
PSNR of directly decrypted image (I)d under different values of parameter σ (dB). (a) L = 128. (b) L = 256. (c) L = 512.
(a)(b)(c)


## 5.3. Comparison with State-of-the-Art Schemes

Since there are few RDHEI schemes for VQ-encoded images, we chose the other five typical RDHEI schemes, i.e., Zhang’s scheme [22], Qian and Zhang’s scheme [26], Yin et al.’s scheme [40], Qian et al.’s scheme [41], and Wu et al.’s scheme [42], for comparing the performance of embedding rate. In detail, the RDHEI schemes [22, 26] focused on uncompressed gray scale images, the schemes [40, 41] were designed for JPEG-encoded images, and the scheme [42] was applied in palette color images. As for the proposed scheme, we utilized four kinds of VQ codebooks with sizes of 128, 256, 512, and 1024, and the parameter σ was set to 0 and 1. It was worth noting that we used the unit of bpi (bits per index) to represent the embedding rate for our RDHEI scheme of VQ-encoded images and the unit of bpp (bits per pixel) for other schemes. Comparison results for the four standard images are given in Table 5. It can be observed from the results that our scheme generally has a competitive performance of embedding rate compared with the schemes in Refs. [22, 26, 40–42].Table 5
Comparisons of embedding rate between the proposed scheme with Refs. [22, 26, 40–42].
SchemesAirplaneBaboonLenaPeppersZhang’s scheme [22]0.05000.05000.05000.0500Qian and Zhang’s scheme [26]0.29520.29520.29520.2952Yin et al.’s scheme [40]0.16470.87670.29190.3060Qian et al.’s scheme [41]0.05650.11510.05590.0649Wu et al.’s scheme [42]0.05550.57300.02040.3420Proposed scheme (L = 128, σ = 0)0.60910.37130.13810.2388Proposed scheme (L = 128, σ = 1)0.84560.41710.29840.2891Proposed scheme (L = 256, σ = 0)1.39190.35360.59090.7957Proposed scheme (L = 256, σ = 1)1.64030.44920.79061.1590Proposed scheme (L = 512, σ = 0)1.82270.37100.80481.1459Proposed scheme (L = 512, σ = 1)2.10100.46201.07561.4823Proposed scheme (L = 1024, σ = 0)2.42250.43581.10241.6953Proposed scheme (L = 1024, σ = 1)2.75440.53711.41422.0040


## 6. Conclusions

Reversible data hiding can be used in many scenarios like security and forensics. In this work, we focus on separable reversible data hiding in encrypted VQ-encoded images, which can achieve high hiding capacity and satisfactory image quality simultaneously. In order to protect the privacy of image contents, content-owner encrypts VQ codebook and index table with stream-cipher and permutation, respectively, and then sends the encrypted, VQ-encoded image to the data hider. In our baseline data-embedding method, the data-hider constructs index groups by grouping one high-occurrence index with one low-occurrence index; while in our optimized method, one high-occurrence index can be grouped with multiple low-occurrence indices to achieve greater hiding capacity. Through further optimizing the coefficient vector for different types of index groups, the optimal hiding capacity can be obtained by modifying the high-occurrence index into the corresponding indices in the same group according to the current to-be-embedded bits. Overall, more concentrated histogram of VQ indices leads to greater hiding capacity, and larger codebook leads to greater hiding capacity but lower directly decrypted image quality. Separable operations of data extraction, image decryption, and image recovery can be realized on the receiver side based on the availability of the encryption and data-hiding keys. Experimental results demonstrate the reversibility, security, hiding capacity, and parameter influence of our scheme, and the superiority compared with some state-of-the-art schemes. In the future work, we will further investigate the RDH for other types of encrypted data, such as video and audio.



---

*Source: 1227926-2022-04-23.xml*