# Improved Lossless Data Hiding for JPEG Images Based on Optimized VLC Mapping

Authors: Yang Zheng; Junhui He
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Most reversible data hiding (RDH) schemes embed data into JPEG images through DCT coefficients modification, but they will cause unavoidable visual distortion in the marked images. Lossless data hiding (LDH) can not only restore the cover JPEG images in a lossless way after extraction of the embedded data but also generate marked images without any visual distortion. For LDH schemes based on variable length code (VLC) mapping, the performance depends mainly on the mapping mode. In this paper, a new LDH scheme for JPEG images based on optimized VLC mapping is proposed. First, for a given mapping mode, a mathematical model of file size change is established. Then, based on the Run/Size frequency of a cover image and the estimation of frequency change caused by simulated data embedding, an iterative method is used to find the optimal mapping mode that leads to the smallest file size increments. Lastly, data is embedded in the cover image using the optimal VLC mapping. Experimental results show that the proposed LDH scheme based on optimized VLC mapping can achieve small increase in the file size of marked images.


---

## Body

## 1. Introduction

Data hiding (also known as information hiding) [1–4] is a technology that embeds data into a cover medium for various purposes. Because of the large amount of redundancy in an image, image has become one of the most commonly used cover media. In some medical, military, or legal applications, any distortion of the cover images may be unacceptable, so it is desirable to be able to restore the cover images after extracting the embedded data. For this purpose, many reversible data hiding (RDH) schemes [5–18] have been proposed. In addition, in order to improve security and protect the privacy of images, some schemes based on encrypted images have been proposed [4, 9, 10, 13, 16–18].Due to the popularity of JPEG images, reversible data hiding in JPEG images has received extensive attention. As described in [19], the JPEG compressed data consists of an ordered collection of parameters, markers, and entropy-coded data segment. Most existing RDH schemes for JPEG images modify the table-specification and entropy-coded data segment to embed data. Therefore, according to the different marker segments modified during data embedding, the JPEG image RDH schemes can be classified into three categories: quantization table modification [20–22], Huffman table modification [23–30], and DCT coefficients modification [31–41]. Wang et al. [22] improved the previous works to embed data in JPEG images by modifying the quantization table. This category of schemes usually achieves a high embedding capacity and results in an unacceptable increase in the file size of marked images. So far, more schemes based on DCT coefficients or Huffman table modification have been proposed.Most RDH schemes based on DCT coefficients modification embed data into JPEG images through histogram shifting. Histogram shifting was first proposed by Ni et al. [5] to embed data into gray-scale uncompressed images. Later, Xuan et al. [31] used histogram shifting to embed data into JPEG images. Huang et al. [32] recommended only using ±1 AC coefficients to embed data while keeping the zero AC coefficients unchanged. Huang’s scheme can achieve high embedding capacity and good visual quality, and the file size of marked image does not increase significantly. By adopting different embedding order, coefficient block ordering, frequency ordering, etc., many recent schemes [33, 34, 36, 40, 41] have improved Huang’s scheme in terms of embedding distortion and file size increase. Lv et al. [35] proposed a novel auxiliary data construction scheme to better serve the image recovery. Li et al. [37] selected appropriate blocks by the optimal threshold to embed data and control visual distortion of marked images. Xie et al. [38] exploited a larger range of coefficients to obtain a higher embedding capacity.When an image is encoded with JPEG, in general, not all variable length codes (VLC) defined in the Huffman table will be used [23]. Therefore, it is possible to embed data into JPEG images by modifying the Huffman table; more specifically, a used VLC is mapped to one or more unused VLCs. Since there is no visual distortion in the marked images, this kind of RDH scheme based on Huffman table modification is also called lossless data hiding (LDH). If the length of all VLCs in each mapping set is the same, in addition to no visual distortion, the file size of an image will remain unchanged after data is embedded [24–27]. Hu et al. [25] first improved the embedding capacity by reordering VLC occurrences in each VLC category. Qiu et al. [26] proposed alternative embedding and further improved the embedding capacity. Zhang et al. [27] traversed more alternative solutions to find the optimal VLC mapping and optimized parameters to reduce the running time. However, the length of most unused VLCs is generally large, while the length of most used VLCs is small. There are not many possible mappings between used VLCs and unused VLCs with the same length. At the same time, the number of used VLCs of large length is also small. Therefore, compared with the RDH schemes based on DCT coefficients modification, the LDH schemes based on VLC mapping between VLCs of the same length have a lower embedding capacity. Qiu et al. [30] first used VLC combinations and permutations to embed data. In addition, they used the relay transfer based algorithm to preprocess the cover JPEG bitstream and then applied the traditional LDH scheme based on the mapping of VLCs with the same length for data embedding. The scheme changed the image file size, but the embedding capacity was greatly improved.If the mapping between VLCs of different lengths is allowed, the embedding capacity of LDH schemes can be greatly improved [25, 28, 29]. But the file size of marked images will inevitably increase. In [25], Hu et al. also extended the algorithm to allow constructing mapping set in all categories. Zhang et al. [28] utilized value transfer matrix to model VLC mapping. Based on the optimal value transfer matrix found iteratively, a reversible mapping is constructed to minimize the increase in file size. It can achieve a better trade-off between capacity and file size, but how to embed data with a mapping set whose number of VLCs is not a positive integer power of two is not clearly described. Du et al. [29] modeled VLC mapping by histogram shifting and obtained the optimal VLC mapping through exhaustive search. While achieving high embedding capacity, the file size increase is better controlled.As described above, compared with the RDH schemes based on DCT coefficients modification, the LDH schemes based on Huffman table modification generate marked images without visual distortion. In order to achieve greater embedding capacity, the LDH scheme may result in a significant increase in the file size of marked images. In this paper, we propose a new LDH scheme for JPEG images based on optimized VLC mapping. The Run/Sizes (RSs) are sorted in descending order based on the number of occurrences in the JPEG bitstream. The sorted frequency histogram helps select the RSs for data embedding. Each selected used RS is mapped to one or multiple unused RSs. For each possible RS mapping, the frequencies of the RSs in the mapping set are modified according to the length of the data to be embedded. Then, VLCs are allocated to the RSs depending on the updated frequencies. More specifically, shorter VLCs are used to encode the more common RSs. The file size increments after simulated data embedding are estimated for each mapping. The optimal mapping mode with the smallest file size increments is employed to embed data into JPEG images. Compared to the state-of-the-art related schemes, the proposed scheme can reduce the increase in the file size of marked images.The rest of this paper is organized as follows. In Section2, the JPEG bitstream structure, the classic LDH scheme based on VLC mapping, and the analysis of related schemes are briefly reviewed. Then, Section 3 describes the proposed scheme in detail. The experimental results and analysis are presented in Section 4. Section 5 concludes the paper.


## 2. Related Work

This section first introduces the simplified JPEG bitstream structure shown in Figure1. Then, a mapping mode is defined to describe the LDH schemes based on VLC mapping. Finally, the related schemes are analyzed.Figure 1
JPEG bitstream syntax structure.


### 2.1. JPEG Bitstream

Although the JPEG standard [19] includes various operations modes, the baseline sequential DCT-based mode is by far the most widely implemented mode. Therefore, the following discussion will be limited to JPEG images encoded in this mode. The bitstream syntax structure can be simplified as in Figure 1. It starts with a start-of-image (SOI) marker, contains JPEG header and entropy-coded data segment, and then ends with an end-of-image (EOI) marker.In the DHT segment of the JPEG header, two lists (i.e., BITS and HUFFVAL) are defined for AC coefficients, where BITS is a 16-byte list giving the number of codes for each codeword length from 1 to 16, and HUFFVAL is a list of 8-bit symbol valuesRS1,RS2,…,RSNN≤256, and N represents the number of RS s in HUFFVAL. Based on BITS and HUFFVAL, the Huffman table for AC coefficients consisting of Huffman codewords and their corresponding 8-bit symbol values can be constructed.The entropy encoded data segment is comprised of multiple minimum coded units (MCUs), and each MCU consists of one code for the DC coefficient, several codes for the AC coefficients, and an end-of-block (EOB) code. If the last AC coefficient in the zig-zag sequence is not zero, the EOB code will be bypassed. Each AC code consists of zero or more consecutive ZRLs, the VLC of the Run/Size and the variable length integer (VLI) of the corresponding non-zero AC coefficient value. Each ZRL represents 16 continuous zero coefficients.


### 2.2. LDH Based on VLC Mapping

In general, there are some VLCs in the AC Huffman table that are not used during JPEG encoding. By mapping a used VLC to one or more unused VLCs, data can be embedded in JPEG images [23–30]. In order to clearly describe the mapping relationships, a mapping mode is defined as follows:(1)M=m1,m2,…,mM,where(2)mi=Ci1,Ci2,…,Cimii=1,2,…,M,is the mapping set of M and ⋅ represents the cardinality of a set. In each mapping set mi; the first element Ci1 is mapped to the remaining mi−1 elements. During data embedding, the used VLC indicated by Ci1 will be replaced with one of the unused VLCs indicated by Ci2,Ci3,…,Cimi according to the data to be embedded. In order to be enable to extract the embedded data, all mapping sets will be saved by modifying the DHT segment. More specifically, RSijj=2,3,…,mi corresponding to Cij in the list HUFFVAL will be modified to be equal to the RSi1 in the same set.Figure2 shows how to embed data into JPEG bitstream using the mapping mode with only a mapping set, i.e., M=m=Ca,Cb,Cc,Cd, where Ca is a used VLC, and Cb, Cc, and Cd are three unused VLCs. The positions of Ca, Cb, Cc, and Cd are 0, 1, 2, and 3 in m, respectively. According to the decimal value of two bits of data, Ca will be replaced with one of the VLC of in m whose position is equal to the decimal value. More specifically, during the data embedding process, Ca will remain unchanged to embed binary data “00” or be replaced with Cb,Cc,Cd to embed “01,” “10,” and “11,” respectively. After the data is embedded, the mapping will be saved by changing RSb, RSc, and RSd in the list HUFFVAL in the DHT segment to RSa.Figure 2
Data embedding via VLC mapping.


### 2.3. Analysis of Related Schemes

Reversible data hiding schemes for JPEG images mainly include LDH schemes based on VLC mapping and RDH schemes based on histogram shifting. Generally, the embedding capacity of LDH schemes is relatively low [24–27]. Different strategies have been exploited to improve the embedding capacity. Hu et al. [25] proposed an extensive algorithm by allowing mapping among VLCs of different lengths, but the file size of marked images will significantly increase. Du et al. [29] reduced the file size increase by finding better VLC mapping based on VLC histogram. But the estimation of VLC frequencies after simulated data embedding does not consider the length of data to be embedded, and the assignment of VLCs to the RSVs does not take updated frequencies into account. In [30], relay transfer will change image file size. The increase in the file size of marked images is difficult to be further optimized according to the length of data to be embedded. Moreover, the embedding performance is unstable for different images. To sum up, it is still a problem to control the file size increase effectively while keeping high embedding capacity. In addition, existing LDH schemes only apply to JPEG images encoded with the default Huffman table, which is another limitation.Compared with LDH schemes, RDH schemes based on histogram shifting will cause visual distortion in the marked images. But they can apply to JPEG images encoded with the optimized Huffman table. Huang et al. [32] achieved lower file size increase and better visual quality by using ±1 AC coefficients and block select strategy to embed data. Hou et al. [36] selected AC coefficients of different frequencies and proposed an advanced block select strategy to achieve better embedding performance. He et al. [41] built a negative model to meet different requirements according to the user’s preference for less image distortion or smaller file size. Their scheme has greatly improved both images quality and file size increments.


## 2.1. JPEG Bitstream

Although the JPEG standard [19] includes various operations modes, the baseline sequential DCT-based mode is by far the most widely implemented mode. Therefore, the following discussion will be limited to JPEG images encoded in this mode. The bitstream syntax structure can be simplified as in Figure 1. It starts with a start-of-image (SOI) marker, contains JPEG header and entropy-coded data segment, and then ends with an end-of-image (EOI) marker.In the DHT segment of the JPEG header, two lists (i.e., BITS and HUFFVAL) are defined for AC coefficients, where BITS is a 16-byte list giving the number of codes for each codeword length from 1 to 16, and HUFFVAL is a list of 8-bit symbol valuesRS1,RS2,…,RSNN≤256, and N represents the number of RS s in HUFFVAL. Based on BITS and HUFFVAL, the Huffman table for AC coefficients consisting of Huffman codewords and their corresponding 8-bit symbol values can be constructed.The entropy encoded data segment is comprised of multiple minimum coded units (MCUs), and each MCU consists of one code for the DC coefficient, several codes for the AC coefficients, and an end-of-block (EOB) code. If the last AC coefficient in the zig-zag sequence is not zero, the EOB code will be bypassed. Each AC code consists of zero or more consecutive ZRLs, the VLC of the Run/Size and the variable length integer (VLI) of the corresponding non-zero AC coefficient value. Each ZRL represents 16 continuous zero coefficients.


## 2.2. LDH Based on VLC Mapping

In general, there are some VLCs in the AC Huffman table that are not used during JPEG encoding. By mapping a used VLC to one or more unused VLCs, data can be embedded in JPEG images [23–30]. In order to clearly describe the mapping relationships, a mapping mode is defined as follows:(1)M=m1,m2,…,mM,where(2)mi=Ci1,Ci2,…,Cimii=1,2,…,M,is the mapping set of M and ⋅ represents the cardinality of a set. In each mapping set mi; the first element Ci1 is mapped to the remaining mi−1 elements. During data embedding, the used VLC indicated by Ci1 will be replaced with one of the unused VLCs indicated by Ci2,Ci3,…,Cimi according to the data to be embedded. In order to be enable to extract the embedded data, all mapping sets will be saved by modifying the DHT segment. More specifically, RSijj=2,3,…,mi corresponding to Cij in the list HUFFVAL will be modified to be equal to the RSi1 in the same set.Figure2 shows how to embed data into JPEG bitstream using the mapping mode with only a mapping set, i.e., M=m=Ca,Cb,Cc,Cd, where Ca is a used VLC, and Cb, Cc, and Cd are three unused VLCs. The positions of Ca, Cb, Cc, and Cd are 0, 1, 2, and 3 in m, respectively. According to the decimal value of two bits of data, Ca will be replaced with one of the VLC of in m whose position is equal to the decimal value. More specifically, during the data embedding process, Ca will remain unchanged to embed binary data “00” or be replaced with Cb,Cc,Cd to embed “01,” “10,” and “11,” respectively. After the data is embedded, the mapping will be saved by changing RSb, RSc, and RSd in the list HUFFVAL in the DHT segment to RSa.Figure 2
Data embedding via VLC mapping.


## 2.3. Analysis of Related Schemes

Reversible data hiding schemes for JPEG images mainly include LDH schemes based on VLC mapping and RDH schemes based on histogram shifting. Generally, the embedding capacity of LDH schemes is relatively low [24–27]. Different strategies have been exploited to improve the embedding capacity. Hu et al. [25] proposed an extensive algorithm by allowing mapping among VLCs of different lengths, but the file size of marked images will significantly increase. Du et al. [29] reduced the file size increase by finding better VLC mapping based on VLC histogram. But the estimation of VLC frequencies after simulated data embedding does not consider the length of data to be embedded, and the assignment of VLCs to the RSVs does not take updated frequencies into account. In [30], relay transfer will change image file size. The increase in the file size of marked images is difficult to be further optimized according to the length of data to be embedded. Moreover, the embedding performance is unstable for different images. To sum up, it is still a problem to control the file size increase effectively while keeping high embedding capacity. In addition, existing LDH schemes only apply to JPEG images encoded with the default Huffman table, which is another limitation.Compared with LDH schemes, RDH schemes based on histogram shifting will cause visual distortion in the marked images. But they can apply to JPEG images encoded with the optimized Huffman table. Huang et al. [32] achieved lower file size increase and better visual quality by using ±1 AC coefficients and block select strategy to embed data. Hou et al. [36] selected AC coefficients of different frequencies and proposed an advanced block select strategy to achieve better embedding performance. He et al. [41] built a negative model to meet different requirements according to the user’s preference for less image distortion or smaller file size. Their scheme has greatly improved both images quality and file size increments.


## 3. Proposed Scheme

For LDH schemes based on VLC mapping, the performance depends mainly on the mapping mode. In order to improve the VLC mapping, the cover JPEG bitstream is parsed to obtain the statistics ofRS s. According to the statistics and the data to be embedded, the optimized mapping mode is found through an iterative method. Then, data is embedded in the cover JPEG image using the optimized mapping mode. The flowchart of the proposed scheme is shown in Figure 3. The detailed processes in the flowchart are described in the following sections. To make the work easier to understand, Table 1 describes and explains the most used notations.Figure 3
The flowchart of the proposed scheme.Table 1
List of notations.
NotationDescriptionCuu-th Huffman codeword generated according to the DHT segmentEMaximum number of steps that W can slidehuFrequency ofCu in the cover bitstreamhu′Frequency ofCu in the marked bitstreamhu′′Sorted frequency ofCu in the marked bitstreamluLength ofCuLWLength of sliding windowmMapping set ofMMMapping modeMcMapping mode candidateMoOptimal mapping modeNNumber of RSs in HUFFVALNunNumber of VLCs (RSs) with the frequency equal to 0PPayload, the length of the embedded dataviEmbedding capacity contributed by allCi1VEmbedding capacity ofMWSliding windowΔLFile size incrementsΔLDHTLength increments of the DHT segmentΔLDHToLength increments of the DHT segment for JPEG images encoded with the optimized Huffman tableΔLECSLength increments of the entropy encoded segmentΔLECSoLength increments of the entropy encoded segment for JPEG images encoded with the optimized Huffman table


### 3.1. File Size Change Model

An LDH scheme based on VLC mapping embeds data in a JPEG image by replacing some of the used VLCs with other unused VLCs according to a VLC mapping mode. Generally, when the lengths of all VLCs in each mapping set are restricted to be the same, the embedding capacity may usually be low. In order to increase the embedding capacity, the lengths of all unused VLCs in every mapping set can be different from the length of the used VLC. However, the file size of the marked JPEG image generated by VLC mapping will increase accordingly. File size changes caused by different mapping modes are different. The file size change model corresponding to a mapping mode will be developed in the following sections.


#### 3.1.1. Estimation of the Embedding Capacity

According to the principle of data embedding described in Section2.2, when using the scheme of VLC mapping based on M defined in (1) to embed data, the embedding capacity V can be estimated by(3)V=∑i=1Mvi=∑i=1Mhi1⋅log2mi,where vi represents the embedding capacity contributed by all Ci1 and hi1 is the frequency of Ci1 in the cover JPEG bitstream. Please note that the estimation of V is mainly used to model file size changes.


#### 3.1.2. Estimation of the Changes in VLC Frequency

Because the data to be embedded is usually encrypted before embedding to further improve security, it is reasonable to assume that the data is binary data with evenly distributed 0s and 1s. Therefore, during data embedding, some VLCs belonging toC11,C21,…,CM1 in the cover JPEG bitstream will be randomly replaced with the unused VLCs in the corresponding m1,m2,…,mM. If PP≤V bits of data are embedded into a JPEG image using M, the frequency of the VLCs belonging to M will change as follows:(4)hij′=V−PV⋅hi1+PV⋅1mi⋅hi1,j=1,PV⋅1mi⋅hi1,j=2,3,…,mi,where hij′ is the frequency of Cij after the data is embedded.The accuracy of the estimation of VLC frequency changes caused by data embedding is important for the design of VLC mapping mode. In most existing related schemes, such as [28, 29], the frequencies of all VLCs in mi after data embedding are assumed to be equal, namely, hij′=1/mi⋅hi1j=1,2,…,mi. For example, 6000 bits of data are embedded into a JPEG image using M=m=Ca,Cb,Cc,Cd, where the frequency of Ca is equal to 4000, and Cb,Cc, Cd are three unused VLCs. According to (3), the embedding capacity obtained by using M is 8000 bits. Then, the frequencies of Ca,Cb,Cc and Cd after data embedding can be estimated using (4). The frequencies of the four VLCs estimated by the proposed scheme and the existing schemes are shown in Figure 4. It can be seen from Figure 4 that the frequencies of Ca,Cb,Cc and Cd estimated by our scheme are 1750, 750, 750, and 750, respectively. However, the existing schemes take it for granted that the frequencies of the four VLCs are all equal to 1000, which may be inaccurate.Figure 4
The estimated frequencies ofCa,Cb,Cc, and Cd in the marked JPEG image with 6000 bits of embedded data. (a) The proposed scheme and (b) existing schemes.
(a)(b)


#### 3.1.3. Codewords Assignment Optimization

As described in the previous section, the frequencies of the VLCs inmi will change during data embedding. More specifically, the frequency of a shorter codeword may decrease, and vice versa. As a result, the RSs with more frequent occurrences are associated with longer codewords, which in turn will lead to an increase in the length of JPEG bitstream. Let Cuu=1,2,…,N represent the u-th Huffman codeword generated according to the DHT segment, and the length of Cu is denoted as lu, which satisfies l1≤l2⋯≤lN. The frequency of Cu in the cover and marked JPEG bitstreams is represented by hu and hu′, respectively. The unreasonable codewords assignment caused by data embedding using M=m1,m2=C1,C3,C6,C8,C2,C9 is illustrated in Figure 5. It can be seen from Figure 5(b) that the RSs with the higher frequencies in the marked JPEG bitstream are not always assigned the shorter codewords. More specifically, the frequencies of RS5, RS4, RS2, RS9, RS1, RS3, RS6, RS7, RS8 satisfy h5′≥h4′≥h2′≥h9′≥h1′≥h3′≥h6′≥h7′≥h8′, but the lengths of the corresponding codewords, l5, l4, l2, l9, l1, l3, l6, l7 and l8, are not in ascending order, so the codewords assignment is not optimal and can be further improved.Figure 5
The frequency histograms of codewords (RSs) in the cover JPEG bitstream and the marked JPEG bitstream generated by data embedding usingM=m1,m2. (a) Original, (b) marked, and (c) sorted form of (b).
(a)(b)(c)In order to ensure that shorter codewords are assigned to the RSs with higher frequencies, the new frequencies of the RSs after data embedding are sorted in descending order. Then, the Huffman codewords are reassigned to the RSs so that the VLCs in order of increasing code length are associated with the RSs in descending order of frequency, as shown in Figure5(c). The sorted frequency of Cu in the marked bitstream is denoted by hu′′. It can be seen from Figure 5(c) that h1′′≥h2′′≥⋯≥h9′′, and l1≤l2≤⋯≤l9. The codewords assignment is optimized.


#### 3.1.4. Estimation of File Size Increments

Based on the descriptions presented in Section2.2, LDH schemes only involve modifying the DHT segment and the entropy encoded data segment of JPEG bitstream. The file size change in the marked JPEG image mainly comes from the changes in the length of these two segments. Thus, the file size increments can be approximately calculated by(5)ΔL=ΔLDHT+ΔLECS,where ΔLDHT and ΔLECS denote the length increments of the DHT segment and the entropy encoded segment, respectively. It should be noted that the length changes caused by byte alignment and stuffing are not included, because it is difficult to predict such changes in advance.Since JPEG images are usually encoded using the default Huffman table, existing LDH schemes [24–30] just replace some used codewords with unused codewords based on M and the data to be embedded without changing the codewords in the Huffman table. Accordingly, the list BITS will keep intact during data embedding. Although the list HUFFVAL needs to be modified to save M, as illustrated in Section 2.2, its length will not change. Therefore, the length of the DHT segment composed of the lists BITS and HUFFVAL will remain unchanged, that is,(6)ΔLDHT=0.In addition, according to the VLC frequency changes and the codewords assignment optimization described in the above two sections, the length increments of the entropy encoded segment can be estimated as follows:(7)ΔLECS=∑u=1Nhu′′−hu⋅lu,where hu is the frequency of Cu in the cover JPEG bitstream and hu′′ denotes the sorted frequency of Cu in the marked JPEG bitstream, as shown in Figures 5(a) and 5(c).When JPEG images are encoded using the optimized Huffman table instead of the default Huffman table, there will be no unused VLCs in the Huffman table. In order to use the VLC mapping defined byM to embed data into such JPEG images, ∑i=1Mmi−1 RSs need to be added to the list HUFFVAL. Since the number of the elements in the list HUFFVAL cannot exceed 256, the total number of RSs including the original and the added ones must not be greater than 256, that is, N+∑i=1Mmi−1≤256. When M is used to embed data, the frequencies of all RSs in the modified list HUFFVAL can be estimated by a method similar to (4). Based on the estimated RS frequencies, the Huffman table consisting of N+∑i=1Mmi−1 codewords, denoted by Ct′|t=1,2,…,N+∑i=1Mmi−1, can be easily generated in order of increasing codeword length. Let ΔLDHTo and ΔLECSo respectively represent the length increments of the DHT segment and entropy encoded segment when the JPEG images encoded with the optimized Huffman table are used as the cover images. The increase in the length of the DHT segment is only caused by the added RSs, so it can be calculated as(8)ΔLDHTo=8×∑i=1Mmi−1,and the increase in the length of the entropy encoded segment resulting from codeword replacement can be estimated by(9)ΔLECSo=∑t=1N+∑i=1Mmi−1ht′′⋅lt−∑u=1Nhu⋅lu,where lt denotes the length of the newly generated codewords.


### 3.2. Optimal Mapping Mode Construction

For the LDH scheme based on VLC mapping, its performance mainly depends on the mapping mode used to embed data. From the descriptions in Section3.1, it can be seen that different mapping modes will result in different increases in the file size of marked JPEG images. In the following sections, we will introduce how to construct an optimal mapping mode based on the proposed file size change model to reduce the increase in file size.


#### 3.2.1. RS Frequency Sorting

For JPEG images encoded with the default Huffman table, shorter codewords are not necessarily assigned to higher frequency RSs, because the default Huffman table is developed from the average statistics of a large number of images and is not optimized for a specific image. The RS frequencies corresponding to the codewords in ascending order of codeword length may not be sorted in descending order, as shown in Figure6(a). According to (3), the contribution of the used VLCs with lower frequency to the embedding capacity is generally less than that of the used VLCs with higher frequency. Therefore, in order to obtain higher embedding capacity, a mapping mode should use these used VLCs corresponding to higher frequency RSs to embed data. To facilitate choosing RSs, the RS frequencies are first sorted in descending order, as shown in Figure 6(b). Moreover, for JPEG images encoded with the optimized Huffman table, the codewords have already been assigned according to the frequencies of RSs. However, the frequencies of the RSs corresponding to the VLCs with the same codeword length may generally not be arranged in descending order (images encoded by IJG toolbox). Therefore, the RS frequencies will also be sorted.Figure 6
The RS frequency histogram of Lena (QF = 70) encoded with the default Huffman table. (a) Original and (b) sorted.
(a)(b)


#### 3.2.2. Mapping Mode Candidates

In order to achieve a balance between performance and efficiency, a sliding windowW with a size of LW is employed in our proposed scheme to traverse the sorted RSs. Let RS1,RS2,…,RSLW denote the RSs in W corresponding to the used VLCs. Then, a mapping mode candidate Mc will be obtained as follows:(10)Mc=m1,m2,…,mLW,subject tomi=Ci1,Ci2,…,Cimi,∑i=1LWmi−1≤Nun,mi=2k,k=0,1,2,3,4,5,6,7,VMc≥P,where Ci1 is the VLC assigned to RSi, Ci2,Ci3,…,Cimi are the unused VLCs assigned to mii=1,2,…,LW, Nun represent the total number of unused VLCs in a JPEG image, and VMc is the embedding capacity that can be obtained by using Mc. For JPEG images encoded with the default Huffman table, Nun is the number of VLCs with the frequency equal to 0, and for JPEG images encoded with the optimized Huffman table, Nun=256−N.In general, higher frequency RSs are assigned shorter VLCs. Mapping a shorter VLC to a longer VLC may result in an increase in the file size of a marked JPEG image. Therefore, if the embedding capacity of the mapping mode constructed from the used VLCs corresponding to lower frequency RSs is sufficient to embedP bits of data, there is no need to use the used VLCs corresponding to the RSs with higher frequency to construct a mapping mode. Thus, W will start to move from the last RS with the lowest frequency, which is not less than P. If the frequency of all RSs is less than P, then W will start to move from the first RS with the highest frequency. It is easy to know that the sliding of W should stop at the N-th position of the sorted RSs. However, W may not need to slide in a large range, as demonstrated in Section 4.1. In our scheme, the parameter E is used to determine when the sliding of W will stop; specifically, E represents the maximum number of steps that W can slide (including the starting position).Figure7 illustrates the sliding of W, where LW=2 and E=5. The third RS is assumed to be the last RS with a frequency not less than P in the RSs in descending order. Therefore, the sliding of W will start at the 3-rd RS and stop at the 7-th RS. In each sliding position of W, two different used VLCs corresponding to the RSs selected by W will be used to construct mapping mode candidates.Figure 7
An example of traversing used RSs with a sliding window of size 2.


#### 3.2.3. Optimal Mapping Mode

WhenW moves from a higher frequency RS toward a lower frequency RS, each used VLC assigned to the RS in W may be mapped to zero or more unused VLCs. Many mapping mode candidates can be constructed as described in Section 3.2.2. Based on the file size change model described in Section 3.1, the optimal mapping mode is defined as the one that will lead to the smallest file size increase.(11)Mo=minimizeMcΔL.Ifmi in Mo satisfies mi=1, it will be removed from Mo because it cannot be used to embed any data. Therefore, the optimal mapping mode can be written as(12)Mo=mo1,mo2,…,moMo,where moi=Coi1,Coi2,…,Coimoii=1,2,…,Mo and moi≥2.


### 3.3. Data Embedding

Using the optimal mapping modeMo obtained above, data can be embedded into a cover JPEG image through VLC mapping shown in Section 2.2. The detailed procedures of data embedding are described as follows. The pseudocode of data embedding is shown in Algorithm 1.Step 1: parse the DHT segment of the cover JPEG bitstream to construct the AC Huffman table, and then calculate the frequency of used VLCs in the entropy encoded data segment.Step 2: based on the file size change model described in Section3.1, find the optimal mapping mode Mo with sufficient embedding capacity to embed data.Step 3: read in a VLC from the entropy encoded data segment. If the VLC is equal toCoi1, log2moi bits of data are embedded by replacing this VLC with one of the VLCs in Coi1,Coi2,…,Coimoi according to the decimal value of the log2moi bits of data. The decimal value corresponds to the position (starting from 0) of VLC in Coi1,Coi2,…,Coimoi, and there is a one-to-one relationship between the decimal value and each position.Step 4: repeat Step 3 until all the data is embedded. Then, modify the DHT segment to save the mapping mode in the list HUFFVAL as shown in Section2.2.Step 5: reconstruct the marked JPEG image with the modified DHT segment and entropy encoded data segment.Algorithm 1: Data embedding.
Input: cover image, embedded data, P, MoOutput: marked image(1)
begin(2)
initializeT=0(3)
whileT<Pdo(4)
read one VLC in the cover JPEG bitstream(5)
ifthe VLC==Coi1then(6)
ifthe remaining bits of embedded data are not enoughthen(7)
fill enough binary ’0’ at the end of the remain bits(8)
end(9)
readlog2moi bits of embedded data(10)
setx as the decimal value of log2moi bits of embedded data(11)
the VLC is replaced byCoix+1(12)
T=T+log2moi(13)
end(14)
end(15)
modify the DHT segment(16)
reconstruct marked image(17)
end


### 3.4. Data Extraction and Image Recovery

When a marked JPEG image is received, the extraction of embedded data and the restoration of the original JPEG image can be completed as follows. The pseudocode of data extraction is shown in Algorithm 2:Step 1: parse the DHT segment of the marked JPEG bitstream to construct the AC Huffman table and the optimal mapping modeMo used during data embedding.Step 2: read in a VLC from the entropy encoded data segment. If the VLC belongs tomoi=Coi1,Coi2,…,Coimoi, it is replaced by Coi1. At the same time, log2moi bits of data are extracted, of which the decimal value is equal to the position of this VLC in moi (starting from 0).Step 3: repeat Step 2 until all the embedded data is extracted. Then, modify the DHT segment to remove the saved mapping mode from the list HUFFVAL.Step 4: reconstruct the cover JPEG image with the modified DHT segment and entropy encoded data segment.Algorithm 2: Data extraction.
Input: marked image, POutput: cover image, embedded data(1)
begin(2)
parse the DHT to construct Huffman table andMo(3)
initializeT=0(4)
whileT<Pdo(5)
read one VLC in the marked JPEG bitstream(6)
ifthe VLC∈moithen(7)
get the position of the VLC inmoi(8)
convert the position value tolog2|moi bits binary data, extract the data(9)
the VLC is replaced byCoi1(10)
T=T+log2moi(11)
end(12)
end(13)
ifT>Pthen(14)
remove the extra ’0’ bits at the end of the extraction data(15)
end(16)
modify the DHT segment(17)
reconstruct cover image(18)
end


## 3.1. File Size Change Model

An LDH scheme based on VLC mapping embeds data in a JPEG image by replacing some of the used VLCs with other unused VLCs according to a VLC mapping mode. Generally, when the lengths of all VLCs in each mapping set are restricted to be the same, the embedding capacity may usually be low. In order to increase the embedding capacity, the lengths of all unused VLCs in every mapping set can be different from the length of the used VLC. However, the file size of the marked JPEG image generated by VLC mapping will increase accordingly. File size changes caused by different mapping modes are different. The file size change model corresponding to a mapping mode will be developed in the following sections.


### 3.1.1. Estimation of the Embedding Capacity

According to the principle of data embedding described in Section2.2, when using the scheme of VLC mapping based on M defined in (1) to embed data, the embedding capacity V can be estimated by(3)V=∑i=1Mvi=∑i=1Mhi1⋅log2mi,where vi represents the embedding capacity contributed by all Ci1 and hi1 is the frequency of Ci1 in the cover JPEG bitstream. Please note that the estimation of V is mainly used to model file size changes.


### 3.1.2. Estimation of the Changes in VLC Frequency

Because the data to be embedded is usually encrypted before embedding to further improve security, it is reasonable to assume that the data is binary data with evenly distributed 0s and 1s. Therefore, during data embedding, some VLCs belonging toC11,C21,…,CM1 in the cover JPEG bitstream will be randomly replaced with the unused VLCs in the corresponding m1,m2,…,mM. If PP≤V bits of data are embedded into a JPEG image using M, the frequency of the VLCs belonging to M will change as follows:(4)hij′=V−PV⋅hi1+PV⋅1mi⋅hi1,j=1,PV⋅1mi⋅hi1,j=2,3,…,mi,where hij′ is the frequency of Cij after the data is embedded.The accuracy of the estimation of VLC frequency changes caused by data embedding is important for the design of VLC mapping mode. In most existing related schemes, such as [28, 29], the frequencies of all VLCs in mi after data embedding are assumed to be equal, namely, hij′=1/mi⋅hi1j=1,2,…,mi. For example, 6000 bits of data are embedded into a JPEG image using M=m=Ca,Cb,Cc,Cd, where the frequency of Ca is equal to 4000, and Cb,Cc, Cd are three unused VLCs. According to (3), the embedding capacity obtained by using M is 8000 bits. Then, the frequencies of Ca,Cb,Cc and Cd after data embedding can be estimated using (4). The frequencies of the four VLCs estimated by the proposed scheme and the existing schemes are shown in Figure 4. It can be seen from Figure 4 that the frequencies of Ca,Cb,Cc and Cd estimated by our scheme are 1750, 750, 750, and 750, respectively. However, the existing schemes take it for granted that the frequencies of the four VLCs are all equal to 1000, which may be inaccurate.Figure 4
The estimated frequencies ofCa,Cb,Cc, and Cd in the marked JPEG image with 6000 bits of embedded data. (a) The proposed scheme and (b) existing schemes.
(a)(b)


### 3.1.3. Codewords Assignment Optimization

As described in the previous section, the frequencies of the VLCs inmi will change during data embedding. More specifically, the frequency of a shorter codeword may decrease, and vice versa. As a result, the RSs with more frequent occurrences are associated with longer codewords, which in turn will lead to an increase in the length of JPEG bitstream. Let Cuu=1,2,…,N represent the u-th Huffman codeword generated according to the DHT segment, and the length of Cu is denoted as lu, which satisfies l1≤l2⋯≤lN. The frequency of Cu in the cover and marked JPEG bitstreams is represented by hu and hu′, respectively. The unreasonable codewords assignment caused by data embedding using M=m1,m2=C1,C3,C6,C8,C2,C9 is illustrated in Figure 5. It can be seen from Figure 5(b) that the RSs with the higher frequencies in the marked JPEG bitstream are not always assigned the shorter codewords. More specifically, the frequencies of RS5, RS4, RS2, RS9, RS1, RS3, RS6, RS7, RS8 satisfy h5′≥h4′≥h2′≥h9′≥h1′≥h3′≥h6′≥h7′≥h8′, but the lengths of the corresponding codewords, l5, l4, l2, l9, l1, l3, l6, l7 and l8, are not in ascending order, so the codewords assignment is not optimal and can be further improved.Figure 5
The frequency histograms of codewords (RSs) in the cover JPEG bitstream and the marked JPEG bitstream generated by data embedding usingM=m1,m2. (a) Original, (b) marked, and (c) sorted form of (b).
(a)(b)(c)In order to ensure that shorter codewords are assigned to the RSs with higher frequencies, the new frequencies of the RSs after data embedding are sorted in descending order. Then, the Huffman codewords are reassigned to the RSs so that the VLCs in order of increasing code length are associated with the RSs in descending order of frequency, as shown in Figure5(c). The sorted frequency of Cu in the marked bitstream is denoted by hu′′. It can be seen from Figure 5(c) that h1′′≥h2′′≥⋯≥h9′′, and l1≤l2≤⋯≤l9. The codewords assignment is optimized.


### 3.1.4. Estimation of File Size Increments

Based on the descriptions presented in Section2.2, LDH schemes only involve modifying the DHT segment and the entropy encoded data segment of JPEG bitstream. The file size change in the marked JPEG image mainly comes from the changes in the length of these two segments. Thus, the file size increments can be approximately calculated by(5)ΔL=ΔLDHT+ΔLECS,where ΔLDHT and ΔLECS denote the length increments of the DHT segment and the entropy encoded segment, respectively. It should be noted that the length changes caused by byte alignment and stuffing are not included, because it is difficult to predict such changes in advance.Since JPEG images are usually encoded using the default Huffman table, existing LDH schemes [24–30] just replace some used codewords with unused codewords based on M and the data to be embedded without changing the codewords in the Huffman table. Accordingly, the list BITS will keep intact during data embedding. Although the list HUFFVAL needs to be modified to save M, as illustrated in Section 2.2, its length will not change. Therefore, the length of the DHT segment composed of the lists BITS and HUFFVAL will remain unchanged, that is,(6)ΔLDHT=0.In addition, according to the VLC frequency changes and the codewords assignment optimization described in the above two sections, the length increments of the entropy encoded segment can be estimated as follows:(7)ΔLECS=∑u=1Nhu′′−hu⋅lu,where hu is the frequency of Cu in the cover JPEG bitstream and hu′′ denotes the sorted frequency of Cu in the marked JPEG bitstream, as shown in Figures 5(a) and 5(c).When JPEG images are encoded using the optimized Huffman table instead of the default Huffman table, there will be no unused VLCs in the Huffman table. In order to use the VLC mapping defined byM to embed data into such JPEG images, ∑i=1Mmi−1 RSs need to be added to the list HUFFVAL. Since the number of the elements in the list HUFFVAL cannot exceed 256, the total number of RSs including the original and the added ones must not be greater than 256, that is, N+∑i=1Mmi−1≤256. When M is used to embed data, the frequencies of all RSs in the modified list HUFFVAL can be estimated by a method similar to (4). Based on the estimated RS frequencies, the Huffman table consisting of N+∑i=1Mmi−1 codewords, denoted by Ct′|t=1,2,…,N+∑i=1Mmi−1, can be easily generated in order of increasing codeword length. Let ΔLDHTo and ΔLECSo respectively represent the length increments of the DHT segment and entropy encoded segment when the JPEG images encoded with the optimized Huffman table are used as the cover images. The increase in the length of the DHT segment is only caused by the added RSs, so it can be calculated as(8)ΔLDHTo=8×∑i=1Mmi−1,and the increase in the length of the entropy encoded segment resulting from codeword replacement can be estimated by(9)ΔLECSo=∑t=1N+∑i=1Mmi−1ht′′⋅lt−∑u=1Nhu⋅lu,where lt denotes the length of the newly generated codewords.


## 3.1.1. Estimation of the Embedding Capacity

According to the principle of data embedding described in Section2.2, when using the scheme of VLC mapping based on M defined in (1) to embed data, the embedding capacity V can be estimated by(3)V=∑i=1Mvi=∑i=1Mhi1⋅log2mi,where vi represents the embedding capacity contributed by all Ci1 and hi1 is the frequency of Ci1 in the cover JPEG bitstream. Please note that the estimation of V is mainly used to model file size changes.


## 3.1.2. Estimation of the Changes in VLC Frequency

Because the data to be embedded is usually encrypted before embedding to further improve security, it is reasonable to assume that the data is binary data with evenly distributed 0s and 1s. Therefore, during data embedding, some VLCs belonging toC11,C21,…,CM1 in the cover JPEG bitstream will be randomly replaced with the unused VLCs in the corresponding m1,m2,…,mM. If PP≤V bits of data are embedded into a JPEG image using M, the frequency of the VLCs belonging to M will change as follows:(4)hij′=V−PV⋅hi1+PV⋅1mi⋅hi1,j=1,PV⋅1mi⋅hi1,j=2,3,…,mi,where hij′ is the frequency of Cij after the data is embedded.The accuracy of the estimation of VLC frequency changes caused by data embedding is important for the design of VLC mapping mode. In most existing related schemes, such as [28, 29], the frequencies of all VLCs in mi after data embedding are assumed to be equal, namely, hij′=1/mi⋅hi1j=1,2,…,mi. For example, 6000 bits of data are embedded into a JPEG image using M=m=Ca,Cb,Cc,Cd, where the frequency of Ca is equal to 4000, and Cb,Cc, Cd are three unused VLCs. According to (3), the embedding capacity obtained by using M is 8000 bits. Then, the frequencies of Ca,Cb,Cc and Cd after data embedding can be estimated using (4). The frequencies of the four VLCs estimated by the proposed scheme and the existing schemes are shown in Figure 4. It can be seen from Figure 4 that the frequencies of Ca,Cb,Cc and Cd estimated by our scheme are 1750, 750, 750, and 750, respectively. However, the existing schemes take it for granted that the frequencies of the four VLCs are all equal to 1000, which may be inaccurate.Figure 4
The estimated frequencies ofCa,Cb,Cc, and Cd in the marked JPEG image with 6000 bits of embedded data. (a) The proposed scheme and (b) existing schemes.
(a)(b)


## 3.1.3. Codewords Assignment Optimization

As described in the previous section, the frequencies of the VLCs inmi will change during data embedding. More specifically, the frequency of a shorter codeword may decrease, and vice versa. As a result, the RSs with more frequent occurrences are associated with longer codewords, which in turn will lead to an increase in the length of JPEG bitstream. Let Cuu=1,2,…,N represent the u-th Huffman codeword generated according to the DHT segment, and the length of Cu is denoted as lu, which satisfies l1≤l2⋯≤lN. The frequency of Cu in the cover and marked JPEG bitstreams is represented by hu and hu′, respectively. The unreasonable codewords assignment caused by data embedding using M=m1,m2=C1,C3,C6,C8,C2,C9 is illustrated in Figure 5. It can be seen from Figure 5(b) that the RSs with the higher frequencies in the marked JPEG bitstream are not always assigned the shorter codewords. More specifically, the frequencies of RS5, RS4, RS2, RS9, RS1, RS3, RS6, RS7, RS8 satisfy h5′≥h4′≥h2′≥h9′≥h1′≥h3′≥h6′≥h7′≥h8′, but the lengths of the corresponding codewords, l5, l4, l2, l9, l1, l3, l6, l7 and l8, are not in ascending order, so the codewords assignment is not optimal and can be further improved.Figure 5
The frequency histograms of codewords (RSs) in the cover JPEG bitstream and the marked JPEG bitstream generated by data embedding usingM=m1,m2. (a) Original, (b) marked, and (c) sorted form of (b).
(a)(b)(c)In order to ensure that shorter codewords are assigned to the RSs with higher frequencies, the new frequencies of the RSs after data embedding are sorted in descending order. Then, the Huffman codewords are reassigned to the RSs so that the VLCs in order of increasing code length are associated with the RSs in descending order of frequency, as shown in Figure5(c). The sorted frequency of Cu in the marked bitstream is denoted by hu′′. It can be seen from Figure 5(c) that h1′′≥h2′′≥⋯≥h9′′, and l1≤l2≤⋯≤l9. The codewords assignment is optimized.


## 3.1.4. Estimation of File Size Increments

Based on the descriptions presented in Section2.2, LDH schemes only involve modifying the DHT segment and the entropy encoded data segment of JPEG bitstream. The file size change in the marked JPEG image mainly comes from the changes in the length of these two segments. Thus, the file size increments can be approximately calculated by(5)ΔL=ΔLDHT+ΔLECS,where ΔLDHT and ΔLECS denote the length increments of the DHT segment and the entropy encoded segment, respectively. It should be noted that the length changes caused by byte alignment and stuffing are not included, because it is difficult to predict such changes in advance.Since JPEG images are usually encoded using the default Huffman table, existing LDH schemes [24–30] just replace some used codewords with unused codewords based on M and the data to be embedded without changing the codewords in the Huffman table. Accordingly, the list BITS will keep intact during data embedding. Although the list HUFFVAL needs to be modified to save M, as illustrated in Section 2.2, its length will not change. Therefore, the length of the DHT segment composed of the lists BITS and HUFFVAL will remain unchanged, that is,(6)ΔLDHT=0.In addition, according to the VLC frequency changes and the codewords assignment optimization described in the above two sections, the length increments of the entropy encoded segment can be estimated as follows:(7)ΔLECS=∑u=1Nhu′′−hu⋅lu,where hu is the frequency of Cu in the cover JPEG bitstream and hu′′ denotes the sorted frequency of Cu in the marked JPEG bitstream, as shown in Figures 5(a) and 5(c).When JPEG images are encoded using the optimized Huffman table instead of the default Huffman table, there will be no unused VLCs in the Huffman table. In order to use the VLC mapping defined byM to embed data into such JPEG images, ∑i=1Mmi−1 RSs need to be added to the list HUFFVAL. Since the number of the elements in the list HUFFVAL cannot exceed 256, the total number of RSs including the original and the added ones must not be greater than 256, that is, N+∑i=1Mmi−1≤256. When M is used to embed data, the frequencies of all RSs in the modified list HUFFVAL can be estimated by a method similar to (4). Based on the estimated RS frequencies, the Huffman table consisting of N+∑i=1Mmi−1 codewords, denoted by Ct′|t=1,2,…,N+∑i=1Mmi−1, can be easily generated in order of increasing codeword length. Let ΔLDHTo and ΔLECSo respectively represent the length increments of the DHT segment and entropy encoded segment when the JPEG images encoded with the optimized Huffman table are used as the cover images. The increase in the length of the DHT segment is only caused by the added RSs, so it can be calculated as(8)ΔLDHTo=8×∑i=1Mmi−1,and the increase in the length of the entropy encoded segment resulting from codeword replacement can be estimated by(9)ΔLECSo=∑t=1N+∑i=1Mmi−1ht′′⋅lt−∑u=1Nhu⋅lu,where lt denotes the length of the newly generated codewords.


## 3.2. Optimal Mapping Mode Construction

For the LDH scheme based on VLC mapping, its performance mainly depends on the mapping mode used to embed data. From the descriptions in Section3.1, it can be seen that different mapping modes will result in different increases in the file size of marked JPEG images. In the following sections, we will introduce how to construct an optimal mapping mode based on the proposed file size change model to reduce the increase in file size.


### 3.2.1. RS Frequency Sorting

For JPEG images encoded with the default Huffman table, shorter codewords are not necessarily assigned to higher frequency RSs, because the default Huffman table is developed from the average statistics of a large number of images and is not optimized for a specific image. The RS frequencies corresponding to the codewords in ascending order of codeword length may not be sorted in descending order, as shown in Figure6(a). According to (3), the contribution of the used VLCs with lower frequency to the embedding capacity is generally less than that of the used VLCs with higher frequency. Therefore, in order to obtain higher embedding capacity, a mapping mode should use these used VLCs corresponding to higher frequency RSs to embed data. To facilitate choosing RSs, the RS frequencies are first sorted in descending order, as shown in Figure 6(b). Moreover, for JPEG images encoded with the optimized Huffman table, the codewords have already been assigned according to the frequencies of RSs. However, the frequencies of the RSs corresponding to the VLCs with the same codeword length may generally not be arranged in descending order (images encoded by IJG toolbox). Therefore, the RS frequencies will also be sorted.Figure 6
The RS frequency histogram of Lena (QF = 70) encoded with the default Huffman table. (a) Original and (b) sorted.
(a)(b)


### 3.2.2. Mapping Mode Candidates

In order to achieve a balance between performance and efficiency, a sliding windowW with a size of LW is employed in our proposed scheme to traverse the sorted RSs. Let RS1,RS2,…,RSLW denote the RSs in W corresponding to the used VLCs. Then, a mapping mode candidate Mc will be obtained as follows:(10)Mc=m1,m2,…,mLW,subject tomi=Ci1,Ci2,…,Cimi,∑i=1LWmi−1≤Nun,mi=2k,k=0,1,2,3,4,5,6,7,VMc≥P,where Ci1 is the VLC assigned to RSi, Ci2,Ci3,…,Cimi are the unused VLCs assigned to mii=1,2,…,LW, Nun represent the total number of unused VLCs in a JPEG image, and VMc is the embedding capacity that can be obtained by using Mc. For JPEG images encoded with the default Huffman table, Nun is the number of VLCs with the frequency equal to 0, and for JPEG images encoded with the optimized Huffman table, Nun=256−N.In general, higher frequency RSs are assigned shorter VLCs. Mapping a shorter VLC to a longer VLC may result in an increase in the file size of a marked JPEG image. Therefore, if the embedding capacity of the mapping mode constructed from the used VLCs corresponding to lower frequency RSs is sufficient to embedP bits of data, there is no need to use the used VLCs corresponding to the RSs with higher frequency to construct a mapping mode. Thus, W will start to move from the last RS with the lowest frequency, which is not less than P. If the frequency of all RSs is less than P, then W will start to move from the first RS with the highest frequency. It is easy to know that the sliding of W should stop at the N-th position of the sorted RSs. However, W may not need to slide in a large range, as demonstrated in Section 4.1. In our scheme, the parameter E is used to determine when the sliding of W will stop; specifically, E represents the maximum number of steps that W can slide (including the starting position).Figure7 illustrates the sliding of W, where LW=2 and E=5. The third RS is assumed to be the last RS with a frequency not less than P in the RSs in descending order. Therefore, the sliding of W will start at the 3-rd RS and stop at the 7-th RS. In each sliding position of W, two different used VLCs corresponding to the RSs selected by W will be used to construct mapping mode candidates.Figure 7
An example of traversing used RSs with a sliding window of size 2.


### 3.2.3. Optimal Mapping Mode

WhenW moves from a higher frequency RS toward a lower frequency RS, each used VLC assigned to the RS in W may be mapped to zero or more unused VLCs. Many mapping mode candidates can be constructed as described in Section 3.2.2. Based on the file size change model described in Section 3.1, the optimal mapping mode is defined as the one that will lead to the smallest file size increase.(11)Mo=minimizeMcΔL.Ifmi in Mo satisfies mi=1, it will be removed from Mo because it cannot be used to embed any data. Therefore, the optimal mapping mode can be written as(12)Mo=mo1,mo2,…,moMo,where moi=Coi1,Coi2,…,Coimoii=1,2,…,Mo and moi≥2.


## 3.2.1. RS Frequency Sorting

For JPEG images encoded with the default Huffman table, shorter codewords are not necessarily assigned to higher frequency RSs, because the default Huffman table is developed from the average statistics of a large number of images and is not optimized for a specific image. The RS frequencies corresponding to the codewords in ascending order of codeword length may not be sorted in descending order, as shown in Figure6(a). According to (3), the contribution of the used VLCs with lower frequency to the embedding capacity is generally less than that of the used VLCs with higher frequency. Therefore, in order to obtain higher embedding capacity, a mapping mode should use these used VLCs corresponding to higher frequency RSs to embed data. To facilitate choosing RSs, the RS frequencies are first sorted in descending order, as shown in Figure 6(b). Moreover, for JPEG images encoded with the optimized Huffman table, the codewords have already been assigned according to the frequencies of RSs. However, the frequencies of the RSs corresponding to the VLCs with the same codeword length may generally not be arranged in descending order (images encoded by IJG toolbox). Therefore, the RS frequencies will also be sorted.Figure 6
The RS frequency histogram of Lena (QF = 70) encoded with the default Huffman table. (a) Original and (b) sorted.
(a)(b)


## 3.2.2. Mapping Mode Candidates

In order to achieve a balance between performance and efficiency, a sliding windowW with a size of LW is employed in our proposed scheme to traverse the sorted RSs. Let RS1,RS2,…,RSLW denote the RSs in W corresponding to the used VLCs. Then, a mapping mode candidate Mc will be obtained as follows:(10)Mc=m1,m2,…,mLW,subject tomi=Ci1,Ci2,…,Cimi,∑i=1LWmi−1≤Nun,mi=2k,k=0,1,2,3,4,5,6,7,VMc≥P,where Ci1 is the VLC assigned to RSi, Ci2,Ci3,…,Cimi are the unused VLCs assigned to mii=1,2,…,LW, Nun represent the total number of unused VLCs in a JPEG image, and VMc is the embedding capacity that can be obtained by using Mc. For JPEG images encoded with the default Huffman table, Nun is the number of VLCs with the frequency equal to 0, and for JPEG images encoded with the optimized Huffman table, Nun=256−N.In general, higher frequency RSs are assigned shorter VLCs. Mapping a shorter VLC to a longer VLC may result in an increase in the file size of a marked JPEG image. Therefore, if the embedding capacity of the mapping mode constructed from the used VLCs corresponding to lower frequency RSs is sufficient to embedP bits of data, there is no need to use the used VLCs corresponding to the RSs with higher frequency to construct a mapping mode. Thus, W will start to move from the last RS with the lowest frequency, which is not less than P. If the frequency of all RSs is less than P, then W will start to move from the first RS with the highest frequency. It is easy to know that the sliding of W should stop at the N-th position of the sorted RSs. However, W may not need to slide in a large range, as demonstrated in Section 4.1. In our scheme, the parameter E is used to determine when the sliding of W will stop; specifically, E represents the maximum number of steps that W can slide (including the starting position).Figure7 illustrates the sliding of W, where LW=2 and E=5. The third RS is assumed to be the last RS with a frequency not less than P in the RSs in descending order. Therefore, the sliding of W will start at the 3-rd RS and stop at the 7-th RS. In each sliding position of W, two different used VLCs corresponding to the RSs selected by W will be used to construct mapping mode candidates.Figure 7
An example of traversing used RSs with a sliding window of size 2.


## 3.2.3. Optimal Mapping Mode

WhenW moves from a higher frequency RS toward a lower frequency RS, each used VLC assigned to the RS in W may be mapped to zero or more unused VLCs. Many mapping mode candidates can be constructed as described in Section 3.2.2. Based on the file size change model described in Section 3.1, the optimal mapping mode is defined as the one that will lead to the smallest file size increase.(11)Mo=minimizeMcΔL.Ifmi in Mo satisfies mi=1, it will be removed from Mo because it cannot be used to embed any data. Therefore, the optimal mapping mode can be written as(12)Mo=mo1,mo2,…,moMo,where moi=Coi1,Coi2,…,Coimoii=1,2,…,Mo and moi≥2.


## 3.3. Data Embedding

Using the optimal mapping modeMo obtained above, data can be embedded into a cover JPEG image through VLC mapping shown in Section 2.2. The detailed procedures of data embedding are described as follows. The pseudocode of data embedding is shown in Algorithm 1.Step 1: parse the DHT segment of the cover JPEG bitstream to construct the AC Huffman table, and then calculate the frequency of used VLCs in the entropy encoded data segment.Step 2: based on the file size change model described in Section3.1, find the optimal mapping mode Mo with sufficient embedding capacity to embed data.Step 3: read in a VLC from the entropy encoded data segment. If the VLC is equal toCoi1, log2moi bits of data are embedded by replacing this VLC with one of the VLCs in Coi1,Coi2,…,Coimoi according to the decimal value of the log2moi bits of data. The decimal value corresponds to the position (starting from 0) of VLC in Coi1,Coi2,…,Coimoi, and there is a one-to-one relationship between the decimal value and each position.Step 4: repeat Step 3 until all the data is embedded. Then, modify the DHT segment to save the mapping mode in the list HUFFVAL as shown in Section2.2.Step 5: reconstruct the marked JPEG image with the modified DHT segment and entropy encoded data segment.Algorithm 1: Data embedding.
Input: cover image, embedded data, P, MoOutput: marked image(1)
begin(2)
initializeT=0(3)
whileT<Pdo(4)
read one VLC in the cover JPEG bitstream(5)
ifthe VLC==Coi1then(6)
ifthe remaining bits of embedded data are not enoughthen(7)
fill enough binary ’0’ at the end of the remain bits(8)
end(9)
readlog2moi bits of embedded data(10)
setx as the decimal value of log2moi bits of embedded data(11)
the VLC is replaced byCoix+1(12)
T=T+log2moi(13)
end(14)
end(15)
modify the DHT segment(16)
reconstruct marked image(17)
end


## 3.4. Data Extraction and Image Recovery

When a marked JPEG image is received, the extraction of embedded data and the restoration of the original JPEG image can be completed as follows. The pseudocode of data extraction is shown in Algorithm 2:Step 1: parse the DHT segment of the marked JPEG bitstream to construct the AC Huffman table and the optimal mapping modeMo used during data embedding.Step 2: read in a VLC from the entropy encoded data segment. If the VLC belongs tomoi=Coi1,Coi2,…,Coimoi, it is replaced by Coi1. At the same time, log2moi bits of data are extracted, of which the decimal value is equal to the position of this VLC in moi (starting from 0).Step 3: repeat Step 2 until all the embedded data is extracted. Then, modify the DHT segment to remove the saved mapping mode from the list HUFFVAL.Step 4: reconstruct the cover JPEG image with the modified DHT segment and entropy encoded data segment.Algorithm 2: Data extraction.
Input: marked image, POutput: cover image, embedded data(1)
begin(2)
parse the DHT to construct Huffman table andMo(3)
initializeT=0(4)
whileT<Pdo(5)
read one VLC in the marked JPEG bitstream(6)
ifthe VLC∈moithen(7)
get the position of the VLC inmoi(8)
convert the position value tolog2|moi bits binary data, extract the data(9)
the VLC is replaced byCoi1(10)
T=T+log2moi(11)
end(12)
end(13)
ifT>Pthen(14)
remove the extra ’0’ bits at the end of the extraction data(15)
end(16)
modify the DHT segment(17)
reconstruct cover image(18)
end


## 4. Experimental Results and Analysis

In our experiments, six commonly used512×512 images from the SIPI image database (http://sipi.usc.edu/database/database.php?volume=misc) and 300 512×512 images randomly selected from the BOSSbase image database [42] are employed to evaluate the performance of the proposed scheme. The six images are shown in Figure 8. All images are converted into grayscale JPEG images with different quality factors, including 30, 50, 70, and 90. Without loss of generality, the data to be embedded is assumed to be a random binary bit sequence. The experimental results are compared not only with three state-of-the-art LDH schemes based on VLC mapping, including Hu et al. [25], Du et al. [29], and Qiu et al. [30], but also with state-of-the-art three RDH schemes based on histogram shifting (DCT coefficients modification), including Huang et al. [32], Hou et al. [36], and He et al. [41]. All program codes are implemented using MATLAB and run on a Windows 10 PC with 3.6 GHz Core i7 CPU and 16 GB memory.Figure 8
The six images used in our experiments. (a) Airplane, (b) Baboon, (c) Couple, (d) Harbour, (e) Lena, and (f) Pepper.
(a)(b)(c)(d)(e)(f)


### 4.1. Choice ofLW and E

Different values ofLW and E will determine the use of different used VLCs to construct mapping mode. The larger their values are, the more mapping mode candidates will be obtained, and a better mapping mode may be found. However, the time required to search for the optimal mapping mode will increase. In order to make a better trade-off between file size increments and running time, different values of LW and E are tested in our experiments.300 images are randomly selected from BOSSbase image database and converted into JPEG images with a quality factor of 70 using the default Huffman table. Then, 3000 : 1000 : 14000 bits (in increments of 1000 bits) of data are embedded in these images respectively. WhenE is fixed at 5, different values of LW are used, namely, 1, 2, 3, 4, 5, and 6. The average file size increments and running time are shown in Figures 9(a) and 9(b), respectively. It can be seen from Figure 9(a) that the file size increments decrease with the increase of LW, which indicates that a larger value of LW should be used. But as shown in Figure 9(b), the running time also increases with the increase of LW; especially when LW=6, the running time increases sharply and is significantly larger than other values. The reason is that is the number of mapping mode candidates will increase exponentially with the increase of LW, and the search for the optimal mapping mode will be more time-consuming. When LW is fixed at 5, E is set to 1, 3, 5, 7, and 9. Figures 9(c) and 9(d) show the average file size increments and running time, respectively. It can be seen from Figures 9(c) and 9(d) that there is no significant difference in the file size increments when E is 3, 5, 7 and 9, and the running time gradually increases with the increase of E. Moreover, for JPEG images encoded with the optimized Huffman table, similar results were observed in our experiments. For brevity, the results are not presented here.Figure 9
Average file size increments and running time of 300 images when differentLW and E are used. (a) File size increments (E = 5), (b) running time (E = 5), (c) file size increments (Lw = 5), and (d) running time (LW = 5).
(a)(b)(c)(d)Based on the above experimental observations,LW is set to 5, and E is set to 3 in the following comparison experiments with other related schemes.


### 4.2. Comparison with LDH Schemes Based on VLC Mapping

In order to make a fair comparison with three state-of-the-art LDH schemes [25, 29, 30] based on VLC mapping, in our experiments, the parameters used in these schemes are set to the values that are beneficial to these schemes as much as possible. More specifically, under the condition that the embedding capacity meets the requirements, the value of TH in [25] is set to the largest possible integer in 4,10 to reduce the increase in file size. Similarly, the length of the starting node (VLC) of a transfer in [30] is set to the largest possible integer in 2,12. And only the embedding capacity contributed by VLC mapping is considered in our experiments. Moreover, if the embedding capacity of one transfer does not meet the requirements, multiple transfers will be used. The parameter U in [29] is set to 5 as suggested by the authors.The six classic images shown in Figure8 are compressed into JPEG images with quality factors of 30, 50, 70, and 90 using the default Huffman table. The different number of binary bits are then embedded into these JPEG images using the proposed scheme and three related LDH schemes. More specifically, 2000 : 2000 : 8000, 3000 : 3000 : 12000, 4000 : 4000 : 16000, and 5000 : 5000 : 20000 bits of data are embedded into the JPEG images with QF = 30, 50, 70 and 90, respectively. It can be seen from Table 2 that, compared with other LDH schemes based on VLC mapping, our proposed scheme achieves the smallest increase in the file size of marked JPEG images in most cases regardless of the quality factor and the length of secret data.Table 2
The file size increments in bits of marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art LDH schemes based on VLC mapping.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[25]513611832184002708878561865627736404961272024792376245512814840283764744863208[30]1144117667207808290410904109841576848241643216464232008592309363098431096[29]−3000−744283253842184568891281407241201182416456226726192159922355230024Ours−3024−69615124256102446807984127763592936014352193045248132961936826384Baboon[25]3520956815336234965600144162382435616970420224315364856813048272724135256888[30]76042444814208304272024912249602528682437624376808200110561110460064[29]−4888−3576−688369678410167576132803824103441213622016−188060241581618568Ours−5296−3736−10481656−936100057449640254484641044815776−27444360901614400Couple[25]46569848159522489679841633628528391041052023168392325422414000298804722462840[30]96098475607608276013488135041356853122147221520215366880404964059240712[29]−2760−59228565640968512091521233645841044015744256247616148802153631952Ours−2984−12881560450457653288160112643512958415520223526048124321975225896Harbour[25]396011216190642524874801696829296399761072023200388805381610664285364239262056[30]111224081204812096435219144191921925678802786427952280406896105924553645648[29]4802608460877284328716812720164405496125361881625416110484881779227160Ours344928454468402424572896561385649129304150322103243272321624025128Lena[25]487211504169282274477521751226488390481093624768369924971212760288884821664024[30]8969045536800020969176100801308841681440015176216889104306643073630800[29]−21683122560684816085464108641515254881096815768234727896158562448030256Ours−2672−6961888462478445608016119923552888815000218965840122561979226768Pepper[25]51201192017560263768184181682696039840112882564837304551528824262564508867368[30]10321040584083282392953697841350442001434414376211683888298162988830040[29]−22728825606840173654968912152163352109441394422040816108961744823712Ours−2584−280188846484564472784012520339287841370418344−80848161269619096In order to verify the effectiveness of our proposed scheme on other images, 300 images are randomly selected from the BOSSbase image database and converted into JPEG images with QF = 30, 50, 70 and 90 using the default Huffman table. 1000 : 1000 : 12000, 2000 : 1000 : 13000, 3000 : 1000 : 14000, and 4000 : 1000 : 15000 bits of data are embedded into each of the 300 JPEG images with quality factors of 30, 50, 70, and 90, respectively. The average file size increments of the marked JPEG images are shown in Figure10. It can be seen from Figure 10 that our proposed scheme still achieves a lower increase in the file size of marked images. The scheme proposed by Hu et al. in [25] causes the largest increase in file size. The reason is that there is no more optimization other than allowing the VLCs in a mapping set to vary in length. Although the embedding capacity is improved, it results in an apparent increase in file size. The file size increments of the scheme proposed by Qiu et al. [30] are still very large in some cases. Especially when QF = 90, the file size increases significantly with the increase of the length of embedded data bits. Du et al. [29] have made some optimizations on the construction of the mapping sets to reduce the file size increments, but there is still room for further improvement, which has been described in Section 2.3. Compared with the related research, the proposed scheme achieves better results.Figure 10
Average file size increments of 300 images encoded with the default Huffman table from the BOSSbase image database. (a) QF = 30, (b) QF = 50, (c) QF = 70, and (d) QF = 90.
(a)(b)(c)(d)


### 4.3. Comparison with RDH Schemes Based on Histogram Shifting

Generally, the RDH schemes based on histogram shifting may generate marked JPEG images encoded with the optimized Huffman table to obtain a smaller increase in file size. In order to compare it with three of such schemes [32, 36, 41], our proposed scheme is extended to the JPEG images encoded with the optimized Huffman table. In our experiments, the weighting factor w in [41] is set to 0.4 and 0.7. The six classic images and 300 images randomly selected from BOSSbase image database are compressed into JPEG images with quality factors of 30, 50, 70, and 90 using the optimized Huffman table. 2000 : 2000 : 8000, 3000 : 3000 : 12000, 4000 : 4000 : 16000, and 5000 : 5000 : 20000 bits of data are embedded into the six JPEG images, and 1000 : 1000 : 12000, 2000 : 1000 : 13000, 3000 : 1000 : 14000, and 4000 : 1000 : 15000 bits of data are embedded into the 300 selected JPEG images.Table3 shows the file size increments of the marked JPEG images generated from the six classic JPEG images. It can be seen from Table 3 that our proposed scheme achieves the smallest file size increments in most cases regardless of the quality factor and the length of secret data. The PSNR values of the marked JPEG images are shown in Table 4. It can be seen from Table 4 that the PSNR values of the marked images generated by our proposed scheme are positive infinity, which indicates that the visual quality of marked images has not decreased. However, the other three RDH schemes cause a certain degree of distortion in the marked images.Table 3
The file size increments in bits of marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art RDH schemes based on histogram shifting.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[32]26805120720098243656734410928134804832921613408177526896127681827223720[36]26564888717695043648716810872133444456900013568176486664124241816823704[41] w=0.426725112734498563736725610936137044640904013936178486520121441762423160[41] w=0.725684760709690803816716010432131124096884813400171445992110321696822768Ours2040404859688016352065049376121123960842411616156565216100561492020160Baboon[32]2864538477841056032486712103521360854641003215216205927168142482094427896[36]276052087640101363080636895521333650481000015024204887600140322073627728[41] w=0.427045344761610552328066729696128805264962413672188086640138882142429064[41] w=0.72160431263048744236850728560111523688788013064180084920106481620824040Ours2256409664408232323259849912119203720853611824159045280102961552820224Couple[32]29685544777697684288773611056142565112996814408183286544129201956826040[36]29445144752098243664742410640142164568924013776185206176125521965625808[41] w=0.427684896715292163376648810176143605000940013416184005496116401800025792[41] w=0.725924768664888963344650410248132004048865612904169125416106881640022968Ours2016408862248096287262729072120723960816812088158005808105281504820152Harbour[32]282452967744997638887648112241477652481035215568203926720118321732024968[36]26885024773698563672732011048147605296994415272205126240115521776025048[41] w=0.4282445926936962438727384108241452851121011215392206805928119921761625592[41] w=0.72320459265928576320063449784128003896859213064180086024117601736023688Ours1992405661048160306461129192120404016798412056161525176100801588819928Lena[32]277654167776973635607280102801284054641043214952181608480138001933624920[36]256854487760976035287376103361285654161003214848182407336137281900025032[41] w=0.4285654007688985635687184103841301652961007214368186566696115601710422592[41] w=0.726165160738492723336711210160127604888988814456180646488114881665622328Ours2016407260408128288063529080120803912800811784159045152101841548820440Pepper[32]255253127584919244887776113761369664721116815296191287456142322061626688[36]266452727568908842727456112001367260001047214208189207096138802057626832[41] w=0.4253652567720951242487680114081396058161000814272186406288120801780024696[41] w=0.7264854247568926440327792114321369656641036814344184325688117681774423616Ours2072397660808024301664649024120324272846412416161685768110321500819792Table 4
The PSNR values of the marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art RDH schemes based on histogram shifting.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[32]45.0539.0936.8235.0047.4341.5738.7636.5349.7944.3741.3238.6855.1251.3748.7346.24[36]45.2240.5837.7535.6647.5342.7439.3436.9349.9145.6842.0638.7755.6951.9249.2846.29[41] w = 0.445.0339.4837.0835.1747.4342.2539.2936.9650.0245.0641.6539.0155.1751.5649.0146.46[41] w = 0.739.1036.6435.1434.1543.5541.5436.7335.9544.2444.2841.2037.8251.3349.9648.3145.56Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Baboon[32]44.1340.3137.7635.9145.3341.2438.5836.4146.5142.5139.5537.2249.2145.2242.6540.64[36]44.3640.5038.1136.2945.4041.5539.0336.9546.8542.8339.8737.4149.4545.3642.7140.66[41] w = 0.444.2940.3137.7935.9745.3341.2538.6036.5646.5642.5539.6037.4250.1345.9643.2741.19[41] w = 0.737.0035.0432.7431.4939.6636.4734.1833.2140.5037.4935.6335.1845.7842.6340.4239.64Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Couple[32]43.3539.3337.1135.5143.8940.5438.5936.9346.2342.5640.4338.7551.3747.7045.3743.65[36]44.0540.3638.0036.2445.5641.9939.5737.5847.7443.8341.3839.1852.7248.3345.7443.82[41] w = 0.443.8739.8637.6535.9745.8841.8639.2937.4046.8343.2441.0239.0553.1749.2846.8844.85[41] w = 0.739.7337.2435.7634.9042.2238.7537.5036.1243.6041.4239.3637.1550.4546.7044.7543.45Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Harbour[32]41.8838.0035.7534.0443.3538.9236.4334.5847.7841.7438.4536.2254.8250.9047.4543.80[36]43.0339.1136.7434.8744.8240.0337.2334.9748.7442.4838.7736.3855.4251.1447.4743.79[41] w = 0.442.1138.5636.2934.6143.7239.4536.8135.0247.9742.1138.8536.5455.4351.3747.8844.36[41] w = 0.739.2136.8435.2533.2139.7835.8435.4133.5338.5936.1334.3933.3852.2750.7547.4337.61Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Lena[32]44.5140.6438.0335.9946.6342.5939.8137.3549.1945.3942.5139.8354.1350.8048.6346.68[36]44.6740.7538.2136.1146.7242.7740.0037.4549.2345.4442.6639.9854.7751.2148.8046.89[41] w = 0.444.5340.6938.1636.1446.6342.7340.0637.6149.8145.6542.8240.2154.8351.6449.1747.20[41] w = 0.742.6738.7736.4935.0743.6042.7038.5037.0948.6744.5540.9939.8351.3049.8549.0946.78Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Pepper[32]44.6040.9237.6335.6946.7243.0740.0037.7149.0645.5142.8040.6853.2049.1246.7344.84[36]44.7241.0138.3936.2746.7743.1940.6238.1749.1645.6343.3141.1754.0750.0547.1845.14[41] w = 0.444.6140.9438.1736.1047.0043.1740.5338.1749.8846.1443.3941.0154.2750.9548.5646.77[41] w = 0.743.8640.9236.6235.7142.3543.0640.0737.7947.0945.5343.0240.4051.2750.1147.9446.37Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞The experimental results of file size increments of the 300 randomly selected images are shown in Figure11. When embedding data of the same length, it can be seen from Figure 11 that our proposed scheme has the smallest file size increments regardless of quality factors. The results of the scheme with w=0.7 proposed by He et al. are close to those of our scheme, especially when the quality factors are 70 and 90. However, the visual distortion of the marked images generated by [41] with w=0.7 may be obvious, while our scheme will not cause visual distortion. Compared with RDH schemes based on histogram shifting for JPEG images, the proposed scheme not only achieves less file size increase in marked images, but also generates marked images without any visual distortion.Figure 11
Average file size increments of 300 images encoded with the optimized Huffman table from the BOSSbase image database. (a) QF = 30, (b) QF = 50, (c) QF = 70, and (d) QF = 90.
(a)(b)(c)(d)


## 4.1. Choice ofLW and E

Different values ofLW and E will determine the use of different used VLCs to construct mapping mode. The larger their values are, the more mapping mode candidates will be obtained, and a better mapping mode may be found. However, the time required to search for the optimal mapping mode will increase. In order to make a better trade-off between file size increments and running time, different values of LW and E are tested in our experiments.300 images are randomly selected from BOSSbase image database and converted into JPEG images with a quality factor of 70 using the default Huffman table. Then, 3000 : 1000 : 14000 bits (in increments of 1000 bits) of data are embedded in these images respectively. WhenE is fixed at 5, different values of LW are used, namely, 1, 2, 3, 4, 5, and 6. The average file size increments and running time are shown in Figures 9(a) and 9(b), respectively. It can be seen from Figure 9(a) that the file size increments decrease with the increase of LW, which indicates that a larger value of LW should be used. But as shown in Figure 9(b), the running time also increases with the increase of LW; especially when LW=6, the running time increases sharply and is significantly larger than other values. The reason is that is the number of mapping mode candidates will increase exponentially with the increase of LW, and the search for the optimal mapping mode will be more time-consuming. When LW is fixed at 5, E is set to 1, 3, 5, 7, and 9. Figures 9(c) and 9(d) show the average file size increments and running time, respectively. It can be seen from Figures 9(c) and 9(d) that there is no significant difference in the file size increments when E is 3, 5, 7 and 9, and the running time gradually increases with the increase of E. Moreover, for JPEG images encoded with the optimized Huffman table, similar results were observed in our experiments. For brevity, the results are not presented here.Figure 9
Average file size increments and running time of 300 images when differentLW and E are used. (a) File size increments (E = 5), (b) running time (E = 5), (c) file size increments (Lw = 5), and (d) running time (LW = 5).
(a)(b)(c)(d)Based on the above experimental observations,LW is set to 5, and E is set to 3 in the following comparison experiments with other related schemes.


## 4.2. Comparison with LDH Schemes Based on VLC Mapping

In order to make a fair comparison with three state-of-the-art LDH schemes [25, 29, 30] based on VLC mapping, in our experiments, the parameters used in these schemes are set to the values that are beneficial to these schemes as much as possible. More specifically, under the condition that the embedding capacity meets the requirements, the value of TH in [25] is set to the largest possible integer in 4,10 to reduce the increase in file size. Similarly, the length of the starting node (VLC) of a transfer in [30] is set to the largest possible integer in 2,12. And only the embedding capacity contributed by VLC mapping is considered in our experiments. Moreover, if the embedding capacity of one transfer does not meet the requirements, multiple transfers will be used. The parameter U in [29] is set to 5 as suggested by the authors.The six classic images shown in Figure8 are compressed into JPEG images with quality factors of 30, 50, 70, and 90 using the default Huffman table. The different number of binary bits are then embedded into these JPEG images using the proposed scheme and three related LDH schemes. More specifically, 2000 : 2000 : 8000, 3000 : 3000 : 12000, 4000 : 4000 : 16000, and 5000 : 5000 : 20000 bits of data are embedded into the JPEG images with QF = 30, 50, 70 and 90, respectively. It can be seen from Table 2 that, compared with other LDH schemes based on VLC mapping, our proposed scheme achieves the smallest increase in the file size of marked JPEG images in most cases regardless of the quality factor and the length of secret data.Table 2
The file size increments in bits of marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art LDH schemes based on VLC mapping.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[25]513611832184002708878561865627736404961272024792376245512814840283764744863208[30]1144117667207808290410904109841576848241643216464232008592309363098431096[29]−3000−744283253842184568891281407241201182416456226726192159922355230024Ours−3024−69615124256102446807984127763592936014352193045248132961936826384Baboon[25]3520956815336234965600144162382435616970420224315364856813048272724135256888[30]76042444814208304272024912249602528682437624376808200110561110460064[29]−4888−3576−688369678410167576132803824103441213622016−188060241581618568Ours−5296−3736−10481656−936100057449640254484641044815776−27444360901614400Couple[25]46569848159522489679841633628528391041052023168392325422414000298804722462840[30]96098475607608276013488135041356853122147221520215366880404964059240712[29]−2760−59228565640968512091521233645841044015744256247616148802153631952Ours−2984−12881560450457653288160112643512958415520223526048124321975225896Harbour[25]396011216190642524874801696829296399761072023200388805381610664285364239262056[30]111224081204812096435219144191921925678802786427952280406896105924553645648[29]4802608460877284328716812720164405496125361881625416110484881779227160Ours344928454468402424572896561385649129304150322103243272321624025128Lena[25]487211504169282274477521751226488390481093624768369924971212760288884821664024[30]8969045536800020969176100801308841681440015176216889104306643073630800[29]−21683122560684816085464108641515254881096815768234727896158562448030256Ours−2672−6961888462478445608016119923552888815000218965840122561979226768Pepper[25]51201192017560263768184181682696039840112882564837304551528824262564508867368[30]10321040584083282392953697841350442001434414376211683888298162988830040[29]−22728825606840173654968912152163352109441394422040816108961744823712Ours−2584−280188846484564472784012520339287841370418344−80848161269619096In order to verify the effectiveness of our proposed scheme on other images, 300 images are randomly selected from the BOSSbase image database and converted into JPEG images with QF = 30, 50, 70 and 90 using the default Huffman table. 1000 : 1000 : 12000, 2000 : 1000 : 13000, 3000 : 1000 : 14000, and 4000 : 1000 : 15000 bits of data are embedded into each of the 300 JPEG images with quality factors of 30, 50, 70, and 90, respectively. The average file size increments of the marked JPEG images are shown in Figure10. It can be seen from Figure 10 that our proposed scheme still achieves a lower increase in the file size of marked images. The scheme proposed by Hu et al. in [25] causes the largest increase in file size. The reason is that there is no more optimization other than allowing the VLCs in a mapping set to vary in length. Although the embedding capacity is improved, it results in an apparent increase in file size. The file size increments of the scheme proposed by Qiu et al. [30] are still very large in some cases. Especially when QF = 90, the file size increases significantly with the increase of the length of embedded data bits. Du et al. [29] have made some optimizations on the construction of the mapping sets to reduce the file size increments, but there is still room for further improvement, which has been described in Section 2.3. Compared with the related research, the proposed scheme achieves better results.Figure 10
Average file size increments of 300 images encoded with the default Huffman table from the BOSSbase image database. (a) QF = 30, (b) QF = 50, (c) QF = 70, and (d) QF = 90.
(a)(b)(c)(d)


## 4.3. Comparison with RDH Schemes Based on Histogram Shifting

Generally, the RDH schemes based on histogram shifting may generate marked JPEG images encoded with the optimized Huffman table to obtain a smaller increase in file size. In order to compare it with three of such schemes [32, 36, 41], our proposed scheme is extended to the JPEG images encoded with the optimized Huffman table. In our experiments, the weighting factor w in [41] is set to 0.4 and 0.7. The six classic images and 300 images randomly selected from BOSSbase image database are compressed into JPEG images with quality factors of 30, 50, 70, and 90 using the optimized Huffman table. 2000 : 2000 : 8000, 3000 : 3000 : 12000, 4000 : 4000 : 16000, and 5000 : 5000 : 20000 bits of data are embedded into the six JPEG images, and 1000 : 1000 : 12000, 2000 : 1000 : 13000, 3000 : 1000 : 14000, and 4000 : 1000 : 15000 bits of data are embedded into the 300 selected JPEG images.Table3 shows the file size increments of the marked JPEG images generated from the six classic JPEG images. It can be seen from Table 3 that our proposed scheme achieves the smallest file size increments in most cases regardless of the quality factor and the length of secret data. The PSNR values of the marked JPEG images are shown in Table 4. It can be seen from Table 4 that the PSNR values of the marked images generated by our proposed scheme are positive infinity, which indicates that the visual quality of marked images has not decreased. However, the other three RDH schemes cause a certain degree of distortion in the marked images.Table 3
The file size increments in bits of marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art RDH schemes based on histogram shifting.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[32]26805120720098243656734410928134804832921613408177526896127681827223720[36]26564888717695043648716810872133444456900013568176486664124241816823704[41] w=0.426725112734498563736725610936137044640904013936178486520121441762423160[41] w=0.725684760709690803816716010432131124096884813400171445992110321696822768Ours2040404859688016352065049376121123960842411616156565216100561492020160Baboon[32]2864538477841056032486712103521360854641003215216205927168142482094427896[36]276052087640101363080636895521333650481000015024204887600140322073627728[41] w=0.427045344761610552328066729696128805264962413672188086640138882142429064[41] w=0.72160431263048744236850728560111523688788013064180084920106481620824040Ours2256409664408232323259849912119203720853611824159045280102961552820224Couple[32]29685544777697684288773611056142565112996814408183286544129201956826040[36]29445144752098243664742410640142164568924013776185206176125521965625808[41] w=0.427684896715292163376648810176143605000940013416184005496116401800025792[41] w=0.725924768664888963344650410248132004048865612904169125416106881640022968Ours2016408862248096287262729072120723960816812088158005808105281504820152Harbour[32]282452967744997638887648112241477652481035215568203926720118321732024968[36]26885024773698563672732011048147605296994415272205126240115521776025048[41] w=0.4282445926936962438727384108241452851121011215392206805928119921761625592[41] w=0.72320459265928576320063449784128003896859213064180086024117601736023688Ours1992405661048160306461129192120404016798412056161525176100801588819928Lena[32]277654167776973635607280102801284054641043214952181608480138001933624920[36]256854487760976035287376103361285654161003214848182407336137281900025032[41] w=0.4285654007688985635687184103841301652961007214368186566696115601710422592[41] w=0.726165160738492723336711210160127604888988814456180646488114881665622328Ours2016407260408128288063529080120803912800811784159045152101841548820440Pepper[32]255253127584919244887776113761369664721116815296191287456142322061626688[36]266452727568908842727456112001367260001047214208189207096138802057626832[41] w=0.4253652567720951242487680114081396058161000814272186406288120801780024696[41] w=0.7264854247568926440327792114321369656641036814344184325688117681774423616Ours2072397660808024301664649024120324272846412416161685768110321500819792Table 4
The PSNR values of the marked images with different quality factors and embedded with different lengths of data using our scheme and three state-of-the-art RDH schemes based on histogram shifting.
ImageSchemePayload (bits) with QF = 30Payload (bits) with QF = 50Payload (bits) with QF = 70Payload (bits) with QF = 902000400060008000300060009000120004000800012000160005000100001500020000Airplane[32]45.0539.0936.8235.0047.4341.5738.7636.5349.7944.3741.3238.6855.1251.3748.7346.24[36]45.2240.5837.7535.6647.5342.7439.3436.9349.9145.6842.0638.7755.6951.9249.2846.29[41] w = 0.445.0339.4837.0835.1747.4342.2539.2936.9650.0245.0641.6539.0155.1751.5649.0146.46[41] w = 0.739.1036.6435.1434.1543.5541.5436.7335.9544.2444.2841.2037.8251.3349.9648.3145.56Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Baboon[32]44.1340.3137.7635.9145.3341.2438.5836.4146.5142.5139.5537.2249.2145.2242.6540.64[36]44.3640.5038.1136.2945.4041.5539.0336.9546.8542.8339.8737.4149.4545.3642.7140.66[41] w = 0.444.2940.3137.7935.9745.3341.2538.6036.5646.5642.5539.6037.4250.1345.9643.2741.19[41] w = 0.737.0035.0432.7431.4939.6636.4734.1833.2140.5037.4935.6335.1845.7842.6340.4239.64Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Couple[32]43.3539.3337.1135.5143.8940.5438.5936.9346.2342.5640.4338.7551.3747.7045.3743.65[36]44.0540.3638.0036.2445.5641.9939.5737.5847.7443.8341.3839.1852.7248.3345.7443.82[41] w = 0.443.8739.8637.6535.9745.8841.8639.2937.4046.8343.2441.0239.0553.1749.2846.8844.85[41] w = 0.739.7337.2435.7634.9042.2238.7537.5036.1243.6041.4239.3637.1550.4546.7044.7543.45Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Harbour[32]41.8838.0035.7534.0443.3538.9236.4334.5847.7841.7438.4536.2254.8250.9047.4543.80[36]43.0339.1136.7434.8744.8240.0337.2334.9748.7442.4838.7736.3855.4251.1447.4743.79[41] w = 0.442.1138.5636.2934.6143.7239.4536.8135.0247.9742.1138.8536.5455.4351.3747.8844.36[41] w = 0.739.2136.8435.2533.2139.7835.8435.4133.5338.5936.1334.3933.3852.2750.7547.4337.61Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Lena[32]44.5140.6438.0335.9946.6342.5939.8137.3549.1945.3942.5139.8354.1350.8048.6346.68[36]44.6740.7538.2136.1146.7242.7740.0037.4549.2345.4442.6639.9854.7751.2148.8046.89[41] w = 0.444.5340.6938.1636.1446.6342.7340.0637.6149.8145.6542.8240.2154.8351.6449.1747.20[41] w = 0.742.6738.7736.4935.0743.6042.7038.5037.0948.6744.5540.9939.8351.3049.8549.0946.78Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞Pepper[32]44.6040.9237.6335.6946.7243.0740.0037.7149.0645.5142.8040.6853.2049.1246.7344.84[36]44.7241.0138.3936.2746.7743.1940.6238.1749.1645.6343.3141.1754.0750.0547.1845.14[41] w = 0.444.6140.9438.1736.1047.0043.1740.5338.1749.8846.1443.3941.0154.2750.9548.5646.77[41] w = 0.743.8640.9236.6235.7142.3543.0640.0737.7947.0945.5343.0240.4051.2750.1147.9446.37Ours+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞+∞The experimental results of file size increments of the 300 randomly selected images are shown in Figure11. When embedding data of the same length, it can be seen from Figure 11 that our proposed scheme has the smallest file size increments regardless of quality factors. The results of the scheme with w=0.7 proposed by He et al. are close to those of our scheme, especially when the quality factors are 70 and 90. However, the visual distortion of the marked images generated by [41] with w=0.7 may be obvious, while our scheme will not cause visual distortion. Compared with RDH schemes based on histogram shifting for JPEG images, the proposed scheme not only achieves less file size increase in marked images, but also generates marked images without any visual distortion.Figure 11
Average file size increments of 300 images encoded with the optimized Huffman table from the BOSSbase image database. (a) QF = 30, (b) QF = 50, (c) QF = 70, and (d) QF = 90.
(a)(b)(c)(d)


## 5. Conclusion

In this paper, we present a new LDH scheme for JPEG images based on optimized VLC mapping. Experimental results and analysis prove the improved performance of our proposed scheme in terms of visual quality and file size increments. The main contributions of this paper are summarized as follows:(1)
According to the VLC mapping mode, the VLC frequency changes after data embedding are accurately modeled. In this way, an accurate estimation of the RS frequency in the marked images is obtained. Based on the estimated RS frequency, the VLC assignment is optimized to ensure that shorter codewords are associated with higher frequency RSs.(2)
A model of file size change caused by data embedding based on VLC mapping is established. The model is suitable for JPEG images encoded with the default Huffman table and the optimized Huffman table.(3)
The optimal VLC mapping mode resulting in smaller increases in the file size of marked JPEG images is found through an iterative method. Moreover, in order to achieve a balance between performance and efficiency, a sliding window is employed to traverse the sorted RS histogram during the search process.



---

*Source: 4858806-2022-04-14.xml*