High Capacity Lossless Data Hiding in JPEG Bitstream Based on General VLC Mapping

Yang Du, Zhaoxia Yin, Xinpeng ZhangIEEE TDSC 2022 · DOI

TL;DR

This paper introduces a novel lossless data hiding (LDH) scheme for JPEG images that achieves high embedding capacity by creatively mapping variable-length codes (VLCs) within the JPEG bitstream. Unlike previous methods that require equal-length VLC mappings, this approach allows for unequal lengths, significantly boosting capacity while maintaining perfect image quality and minimizing file size increases.

What Problem Does This Paper Address?

JPEG is the most ubiquitous image format, making it a prime target for data hiding applications. However, existing reversible data hiding (RDH) schemes for JPEG images often suffer from either significant visual distortions or substantial increases in file size when embedding secret data. Lossless data hiding (LDH), a subset of RDH, aims to preserve the original image quality perfectly. While some LDH schemes exist for uncompressed images, their adaptation to the compressed JPEG domain is challenging. Previous JPEG LDH schemes fall into two categories: DCT-based (modifying discrete cosine transform coefficients) and VLC-based (modifying variable-length codes). DCT-based methods often introduce distortions, while existing VLC-based methods, though lossless, have limited embedding capacity due to constraints on VLC mapping. This paper addresses the need for a high-capacity, lossless JPEG data hiding scheme that overcomes the capacity limitations of existing VLC-based methods without compromising visual quality or excessively increasing file size.

Methods

The proposed scheme, termed General VLC Mapping (GVM), operates on the JPEG bitstream's entropy-coded data. The core idea is to leverage unused Variable Length Codes (VLCs) to embed secret data by replacing used VLCs with unused ones. The novelty lies in the "General VLC Mapping" strategy, which allows the lengths of used and unused VLCs within a mapping set to be unequal. This contrasts with prior VLC-based schemes that enforced equal lengths, thereby limiting capacity.

The process involves several key steps:

  1. Preprocessing:
    • VLCs Parsing: The JPEG bitstream is parsed to identify all VLCs and their frequencies. The Huffman table from the DHT segment is used for this.
  2. RSVs Reordering: The Run/Size Value (RSV) codes corresponding to VLCs are reordered based on their frequencies in descending order. This aims to reduce coding redundancy and create a sharper histogram of RSVs, making them more amenable to modification.
  3. Embedding Manner Selection: The paper discusses two embedding manners:
  4. Direct Mapping (DM): Used in previous VLC-based schemes, where used and unused VLCs have the same length. This preserves file size but limits capacity.
  5. Histogram Shifting (HS): The proposed approach, which converts the VLC mapping problem into a histogram shifting problem. This allows for unequal VLC lengths in a mapping set, increasing capacity but potentially leading to file size expansion. The HS manner is chosen for its higher capacity potential.
  6. Construction of GVM Relationship:
    • A simulated embedding model is established to evaluate different GVM relationships.
  7. Key parameters are identified: selected "peak bins" (RSVs with high frequencies) and "zero bins" (RSVs with zero frequencies) to be used for embedding.
  8. Constraints are defined to guide the selection of these parameters, aiming to minimize file size increments while achieving the desired payload.
  9. The optimal GVM relationship ($G_{opt}$) is determined by finding the combination of parameters that results in the smallest simulated file size increment.
  10. Data Embedding & Extraction:
    • Secret data is embedded by replacing original VLCs with mapped VLCs according to the optimal GVM relationship.
  11. Crucially, the file header (specifically, the RSV sequence in the DHT segment) is modified to reflect the mapping. This ensures that the marked JPEG image can be decoded without error and preserves visual quality. The modification ensures that the RSV corresponding to the original VLC and the mapped VLC are the same, thus maintaining the integrity of the bitstream for the decoder.

Datasets

The paper evaluates its proposed scheme using:

  • Six 512x512x8-bit grayscale test images from the USC-SIPI database: Baboon, Lena, Tiffany, Peppers, Elaine, and Airplane. These were converted to grayscale JPEG images with a Quality Factor (QF) of 70.
  • 200 images randomly selected from the UCID database. These were converted into grayscale JPEG images with four QFs: 30, 50, 70, and 90.

All test JPEG images were compressed using the default Huffman table via the IJG toolbox to ensure a fair comparison with previous methods that also rely on this default table. No new benchmarks were introduced; rather, existing datasets were used to compare against prior work.

Key Insights and Ideas

  • Unequal VLC Lengths Unlock Capacity: The most significant insight is that allowing unequal lengths for used and unused VLCs in a mapping set is key to achieving high embedding capacity in the JPEG bitstream. This breaks a fundamental limitation of previous VLC-based schemes.
  • Histogram Shifting for VLCs: Adapting the histogram shifting technique, commonly used for uncompressed images, to the VLC domain of JPEG bitstreams provides a powerful framework for managing capacity and file size trade-offs.
  • RSV Reordering for Optimization: Reordering the Run/Size Value (RSV) codes based on frequency sharpens the histogram, making it more suitable for modification and potentially reducing coding redundancy, which indirectly aids in file size preservation.
  • Simulated Embedding for Optimal GVM: Using a simulated embedding model to evaluate numerous feasible GVM relationships is crucial for finding the optimal mapping that balances embedding capacity and file size increments.
  • Header Modification for Lossless Decoding: Modifying the DHT segment's RSV sequence to match the mapped VLCs is essential for ensuring that the marked JPEG image is perfectly decodable by standard JPEG decoders, thus guaranteeing lossless data hiding and no visual distortion.

Key Results

  • High Embedding Capacity: The proposed GVM-based scheme achieves significantly higher embedding capacities compared to previous VLC-based schemes (e.g., Qian and Zhang [25], Hu et al. [26], Qiu et al. [27]). For instance, with parameters (1,2, {1,1}), capacities in the tens of thousands of bits are achieved, far exceeding the hundreds or low thousands of bits from prior methods.
  • Minimal File Size Increments: While allowing unequal VLC lengths inherently introduces some file size expansion, the proposed HS embedding manner and the optimization process effectively minimize these increments. In many cases, the "pure file size increments" (PFI), which accounts for pre-existing coding redundancy, are significantly smaller than the embedding capacity and often smaller than the file size increments of previous schemes. Some PFI values were even negative, indicating that the scheme can leverage coding redundancy to offset embedding-induced expansion.
  • Perfect Visual Quality: The scheme guarantees lossless data hiding, meaning the marked JPEG images have no visual distortion. This is confirmed by the reported PSNR values of +∞ for all tested images and payloads.
  • Comparison with DCT-based Schemes: The paper also compares its file size increments with DCT-based schemes, showing that its PFIs are often much smaller, and its "grass file size increments" (GFI, which includes shifting and embedding effects) are competitive or better.

Limitations and Future Work

  • Dependency on Default Huffman Table: A significant limitation acknowledged is that the proposed scheme is designed for JPEG images compressed using the default Huffman table. It does not directly apply to images compressed with optimized Huffman tables, which are often used for better compression efficiency.
  • Computational Complexity: While not explicitly detailed as a limitation, the process of generating a complete solution space and simulating embedding for optimization suggests a potentially high computational cost for finding the optimal GVM relationship.
  • Future Work:
    • Optimized Huffman Tables: The authors plan to extend the scheme to handle JPEG images compressed with optimized Huffman tables.
  • Faster Optimization: Developing a more efficient algorithm to solve the optimization problem for finding the GVM relationship is a key future direction.
  • Further Capacity/Size Trade-offs: Exploring more advanced GVM strategies and parameter combinations to further fine-tune the trade-off between embedding capacity and file size preservation.

Summary updated

BibTeX
@article{du2022high,
  author = {Yang Du and Zhaoxia Yin and Xinpeng Zhang},
  title = {{High Capacity Lossless Data Hiding in JPEG Bitstream Based on General VLC Mapping}},
  journal = {IEEE Trans. Dependable Secur. Comput.},
  year = {2022},
  doi = {10.1109/tdsc.2020.3013326},
}
Figure