Traditional steganography hides secret data by modifying the least significant bits (LSBs) of an image. While effective at keeping the data hidden from human eyes, this process permanently discards the original image information. In highly sensitive fields like medical imaging, military intelligence, or legal forensics, even a single bit of permanent distortion is unacceptable.
Reversible Data Hiding (RDH) solves this dilemma. It ensures that after the secret message is extracted at the receiver's end, the original cover medium can be perfectly reconstructed, bit-for-bit. The secret to achieving this perfect reversibility lies in exploiting the statistical redundancy of the host data through a technique called Histogram Shifting (HS), often paired with Prediction-Error Expansion (PEE).
The Mechanics of Histogram Shifting
To understand why histogram shifting works, imagine a frequency distribution (a histogram) of values within a file. These values could be pixel intensities in an image, or even the weights of a deep convolutional neural network, as demonstrated by Guan et al. (2021).
If we can find a highly frequent value (the "peak point") and an entirely unused value (the "zero point") in this histogram, we can systematically create an empty slot to store our data.
Original Histogram:
|
|
| | |
______| | |______
Peak Zero
Shifted Histogram (Creating a Gap):
|
|
| . | |
______| . | |______
Peak Gap Zero
By shifting all values between the peak and the zero point by exactly one unit toward the zero point, we leave the peak value isolated next to an empty, "vacant" bin. We can then embed a binary secret bit into each occurrence of the peak value:
- If the secret bit is
0, we leave the value at the peak. - If the secret bit is
1, we move it into the newly created vacant bin.
Because this modification is entirely deterministic, the decoder can read the values, extract the secret bits based on whether a value sits at the peak or in the adjacent bin, and then shift the remaining values back to their original positions. This completely restores the original data without any loss.
To scale up this capacity, Jia (2019) showed that identifying multiple peak values allows the system to create multiple gaps simultaneously, effectively multiplying the available embedding slots. Alternatively, Horng et al. (2021) demonstrated that preprocessing steps, such as an XOR operation, can artificially create "vacating bands" in the histogram, using an adjustable threshold to dynamically balance embedding capacity against visual quality.
Sharpening the Peak with Prediction-Error Expansion
The capacity of a basic histogram shifting scheme is strictly limited by the height of the histogram's peak. Raw pixel values in natural images are typically distributed across a wide spectrum, resulting in a relatively flat histogram with short peaks.
To maximize capacity, researchers do not shift raw pixel values. Instead, they shift prediction errors.
Because neighboring pixels in an image are highly correlated, a pixel's value can be accurately guessed using its neighbors via spatial interpolation or context modeling. The difference between the actual pixel value and its predicted counterpart is the prediction error. When you plot these errors, they form an incredibly sharp, narrow histogram centered tightly around zero.
Raw Pixel Histogram (Flat) Prediction Error Histogram (Sharp Peak)
_ _ |
_ | || | _ |
| |_| || |_| | | | |
|____________| ____| | |____
This sharp distribution enables Prediction-Error Expansion (PEE). As explained by Bharanitharan et al. (2016) and Wang et al. (2015), small prediction errors are mathematically expanded to carry information, while larger prediction errors are shifted outward to prevent value collisions.
Unidirectional shifting can cause a noticeable drift in an image's overall brightness, degrading its visual quality. To counteract this, Dai et al. (2011) introduced alternating error expansion. By alternating between adding and subtracting values in successive processing passes, the modifications to the histogram occur bidirectionally. This balances out the pixel value adjustments, maintaining a much higher peak signal-to-noise ratio (PSNR) at equivalent data capacities.
Multi-Layer and Compressed Domain Scaling
As the field has matured, the focus has shifted toward embedding data across multiple layers or directly within compressed domains to maximize payload capacity.
One prominent strategy is bit-plane decomposition. Abbasi et al. (2018) demonstrated that breaking an image down into its constituent bit-planes and sequentially embedding data across multiple layers allows for a highly tunable balance between data payload and visual fidelity. In a similar vein, Feng et al. (2021) highlighted how combining the hierarchical coding of most significant bits (MSBs) with the compression of least significant bits (LSBs) can safely carve out high-capacity embedding spaces.
When images are stored in compressed formats—such as Block Truncation Coding (BTC)—the histogram shifting mechanism must adapt to the underlying compressed data structures. Lin et al. (2019) showed that data can be embedded at two levels simultaneously by defining zero and peak points within both the quantization levels and the bitmaps of edge-blocks.
To optimize this compressed space, Lin et al. (2024) designed a multi-layer embedding strategy for bitmaps that uses side-match techniques for the initial layers and Huffman coding for subsequent layers, compressing the remaining metadata to reclaim unused bits for the secret payload.
Finally, capacity can be expanded by distributing the data across multiple images or dimensions. Xu et al. (2024) proposed a two-tier bit-flipping strategy for dual images, where data is embedded in distinct, sequential stages across a pixel pair. By combining these multi-layer approaches with lossless compression techniques like arithmetic coding to minimize auxiliary overhead—as shown by Yeh et al. (2025)—modern RDH frameworks achieve massive data payloads while guaranteeing the flawless, bit-perfect restoration of the original media.
Key Foundational Work
Reversible Watermarking Using Adaptive Edge-Guided Interpolation (2011) — contributed 3 concept elements to this direction.
Reversible Data Hiding for High Quality Using Secret Data Transformation Strategy (2015) — contributed 1 concept elements to this direction.
A novel information hiding scheme based on line segments (2015) — contributed 1 concept elements to this direction.