Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding (Chen and Wornell, 2001)
Quantization index modulation, or QIM, embeds information by choosing a quantizer and applying it to a host signal. A quantizer replaces an input with an allowed reconstruction value; the host is the signal carrying the message. Chen and Wornell address the competing demands of embedding rate, signal distortion and recovery after processing or deliberate attacks. They focus on decoding without the original host. Their dither-modulation construction uses shifted versions of a common quantizer. Chen and Wornell, Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding (2001).
Why must the encoder account for the host signal?
The host can interfere with the message during decoding. Adding a message-dependent signal leaves the decoder observing both that signal and the unknown host. Section III argues that this interference restricts embedding when the host dominates the channel disturbance. A channel describes processing between embedding and reception.
The authors use the encoder’s knowledge of the host to reject that interference. They seek reconstruction sets whose identity remains recoverable as the host varies. Embedding rate counts message bits per host sample; distortion measures the change caused by embedding. Robustness concerns the disturbances under which decoding remains reliable.
Why assign a separate quantizer to each message?
Section IV requires each embedding function to keep its output near the host, while separating outputs belonging to different messages. Overlapping reconstruction sets can make messages ambiguous even before processing. QIM gives each message its own reconstruction set and moves the host to a nearby point in that set.
The authors connect each design choice to a different requirement. The number of quantizers determines rate. Quantization cells, the input regions mapped to reconstruction points, determine distortion through their size and shape. Minimum distance, the closest separation between different messages’ reconstruction sets, determines tolerance to bounded disturbances.
Why build the quantizers from shifted grids?
Dither modulation makes every quantizer a shifted copy of a base quantizer. A dither is the offset defining a shift. Section V uses this shared structure for low-complexity implementation. For binary embedding, the offsets differ by half a step to maximize separation. A bit is a message symbol with value zero or one.
Section V-A’s construction proceeds as follows:
- Optionally encode message bits with an error-correction code, adding redundancy.
- Divide the host into nonoverlapping blocks and assign a coded bit to each block.
- Construct paired offsets and a base quantizer for each block.
- Select the bit’s offset, quantize the shifted host and subtract the offset.
For a scalar input, Delta is the grid spacing, x the host value, b the bit and s the embedded value:
q(v) = Delta * round(v / Delta)
s = q(x + d(b)) - d(b)
How does the decoder choose a message without the host?
The minimum-distance decoder searches the reconstruction sets using the received value y. Section IV emphasizes its search domain:
“the minimum-distance decoder needs to choose from all reconstruction points of the quantizers”
— Chen and Wornell (2001), Section IV
For nearest-point quantizers, apply each candidate quantizer to y and select the nearest result. A disturbance shorter than half the minimum separation guarantees correct decoding. For binary scalar dither modulation, this gives a quarter-step disturbance bound.
r(b) = q(y + d(b)) - d(b)
b_hat = argmin_b abs(y - r(b))
Take illustrative values x = 13.3, Delta = 8, d(0) = -2, and d(1) = 2. For bit 0, rounding 11.3 to 8 gives s = 10; for bit 1, rounding 15.3 to 16 gives s = 14. Sending 14 and adding a disturbance of 1.5 gives y = 15.5, nearer the bit-1 grid at 14 than the bit-0 grid at 18. Their distances are 1.5 and 2.5, and disturbances smaller than Delta/4 = 2 preserve the bit.
Why quantize a projection instead of every sample?
A projection is a weighted sum of host samples. Spread-transform dither modulation, or STDM, quantizes a projection whose squared weights sum to one and preserves perpendicular components. Section V-B motivates this through decision geometry and distortion distribution.
Figures 4–6 hold minimum distance and average distortion fixed while changing the allocation across transformed components. Concentrating quantization in a projection enlarges the correct-decision region in the illustrated case. The marked point s in Figure 6 lies between the dashed decision boundaries. Spreading the projection vector over space, time or frequency also spreads the resulting distortion. Existing spread-spectrum systems can retain their other processing while replacing their embedding operation with dithered quantization.

Chen and Wornell (2001), Figure 6. Marked point and decision strip.
How do step size and coding set the embedding strength?
Increasing the grid step increases both reconstruction-set separation and quantization error. Section V-A approximates the host distribution within small cells as uniform in the high-fidelity regime, where embedding distortion is small relative to host energy. Under that assumption, a scalar quantizer’s expected squared error is:
expected_squared_error = Delta^2 / 12
Error-correction coding supplies another control. Its minimum Hamming distance is the fewest differing bits between distinct valid coded messages. Those differences accumulate separation across blocks. The authors derive a distortion-normalized minimum distance linking the code’s separation benefit, rate and robustness. They also allow uneven distortion allocation across transformed components, or coefficients, while preserving that normalized distance.
Why add back part of the quantization error?
Section IV-A enlarges the quantizer spacing, then adds back a fraction of the difference between the host and its quantized value. This distortion-compensated QIM, or DC-QIM, trades increased separation against interference introduced by the added-back error.
Let Q_scaled denote the message quantizer with spacing enlarged by dividing by alpha. Let D_s be mean embedding distortion and sigma_n^2 the channel-noise variance. The distortion-to-noise ratio, DNR, compares these powers:
s = Q_scaled(x, m) + (1 - alpha) * (x - Q_scaled(x, m))
DNR = D_s / sigma_n^2
alpha_opt = DNR / (1 + DNR)
The authors choose this parameter to maximize separation relative to total interference. Suitably coded DC-QIM also reaches capacity for Gaussian, or bell-shaped, noise with that setting. Capacity is the greatest asymptotically reliable rate as signal length grows.
All parts of the method
The encoder selects a representation of the host, optionally codes the message, and embeds by choosing a quantizer. Dither modulation realizes that selection through offsets; STDM applies it to projections. Distortion compensation can modify the quantized output. Processing or an attack then changes the embedded signal. The decoder uses the shared quantizer settings and its decision rule to recover the message. The diagram follows scalar dither embedding and nearest-grid decoding.
What experiments did the authors run?
The authors analytically evaluate projection methods, Gaussian capacity, hybrid transmission, capacity gaps, private-key attacks, bounded perturbations and bounded host distortion.
Projection methods at equal distortion
Section V-B uses signal projections with matched embedding distortion and disturbance energy. Signal-to-noise ratio, or SNR, compares signal power with interference power; decibels (dB) express power ratios logarithmically. For uncorrelated host and noise at host SNR 30 dB, the authors calculate a 28.8 dB STDM decision-SNR advantage over additive spread spectrum. Against binary spread low-bit modulation (LBM), which replaces low-order bits of a quantized host, the advantage is 2.43 dB. Appendix A gives a limit of 3 dB as the number of message symbols grows.
Gaussian capacity and host availability
Section VII-A uses independent Gaussian host samples and additive white Gaussian noise: independent bell-shaped disturbances with common variance, or squared spread. Varying DNR yields C = 0.5 * log2(1 + DNR) bits per sample. The authors derive this capacity for suitably coded DC-QIM, independently of host variance and whether the decoder knows the host. Section VII-C5 bounds the known-host gap for coded uniform scalar dither modulation by 1.53 dB, with a limiting rate loss of 0.2546 bits per dimension. Section VI-B also establishes regular QIM’s optimality for discrete-valued outputs over an error-free digital channel.
Hybrid transmission and received quality
Section VII-B treats Gaussian analog and coded digital hosts under additive noise. Embedding adds distortion to the received host. For an analog host, the authors derive 0.3322 embedded bits per second per hertz per decibel of received-quality loss. For a digital host, the combined host and embedded rates equal the capacity of a single digital signal using the same total power. Preserving the original host code depends on its noise margin.
Regular QIM rate and quality gaps
Section VII-C1 optimizes spreading under the Gaussian model. Figure 9 bounds regular QIM’s required DNR relative to capacity: at most about 4.3 dB at low rates, tending to no gap at high rates. Figure 10 expresses received-host quality loss. Near 1 bit per second per hertz, QIM requires at most 1.6 dB additional loss beyond DC-QIM’s approximately 3 dB.

Chen and Wornell (2001), Figure 9. Low-rate DNR gap.

Chen and Wornell (2001), Figure 10. Received-quality gap near its peak.
Uncoded error probabilities and additive embedding
Sections VII-C2–C4 retain the Gaussian channel. At low rates and bit-error probability 10^-6, uncoded binary STDM is about 13.6 dB from capacity; spread LBM is about 16 dB away. Figure 11 plots the STDM bound against rate-normalized DNR, meaning DNR divided by embedding rate. Coding, vector quantization and nondithered quantization can reduce the gap by at least 9.3 dB. The authors cite practical coding with compensation closing about 6 dB. Coded additive spread spectrum instead suffers a multiplicative required-DNR penalty of 1 + host_SNR, disappearing as host interference vanishes.

Chen and Wornell (2001), Figure 11. Low-error end of the STDM curve.
Private-key attacks
Section VIII-A gives the attacker the codebook distribution but withholds the actual codebook. Attack strength is bounded expected squared perturbation energy. For a white Gaussian host, the authors use Moulin and O’Sullivan’s results to derive capacity-achieving DC-QIM and its compensation parameter. They extend the conclusion to a high-fidelity limit for zero-mean, finite-variance hosts with bounded continuous probability densities.
Fully informed bounded perturbations
Section VIII-B1 lets the attacker know the embedded signal and algorithm, constraining output distance from the embedded signal. The authors guarantee error-free minimum-distance decoding when total perturbation energy is less than one quarter of squared minimum distance. Uniform binary dither modulation has a 2.43 dB advantage over corresponding generalized LBM. Additive spread spectrum has zero host-blind minimum distance in this model.
Fully informed bounded host distortion
Section VIII-B2 constrains expected output error relative to the original host. The attacker knows the embedding process and has partial host knowledge through a conditional distribution. Table I reports high-fidelity distortion penalties: attack distortion divided by embedding distortion. Regular QIM with centroid reconstruction points requires additional distortion. With contiguous quantization cells, DC-QIM can be inverted to restore the host; additive embedding can be subtracted. LBM permits outputting the coarse quantizer’s reconstruction point.
| Method | Distortion penalty |
|---|---|
| Regular QIM | > 0 dB |
| Binary dither modulation, uniform scalar quantization | > 0 dB; ≤ 2.43 dB |
| DC-QIM | −∞ dB |
| Additive spread spectrum | −∞ dB |
| LBM | ≤ 0 dB |
| Binary LBM, uniform scalar quantization | -2.43 dB |
Source: Chen and Wornell (2001), Table I.
Our test: How does step size affect image bit recovery?
We re-implemented the method ourselves because we did not find the authors’ code. Our code and numeric results are on GitHub.
We used USC-SIPI Airplane and Boat. The discrete cosine transform, or DCT, expresses an image block as weights on cosine brightness patterns. We embedded one bit per block. The payload is the embedded message. Bit error rate, or BER, is the fraction of bits decoded incorrectly. Peak signal-to-noise ratio, or PSNR, summarizes squared pixel differences from the original in decibels. Noise standard deviation measures the spread of brightness changes.
| Setting | Value |
|---|---|
| Preparation | 512×512 grayscale |
| Blocks; payload | 8×8; 4,096 bits |
| Step sizes | 8, 16, 32, 64 |
| JPEG qualities | 90, 70, 50, 30 |
| Noise standard deviations | 1, 3, 6 brightness levels |
The embedding panels show step size 32. Absolute differences are multiplied by 16 for display. The attack panels show each JPEG setting and noise level applied separately. JPEG is lossy image compression; its quality setting controls compression level.




The table pairs un-attacked PSNR with BER after JPEG quality 70 and noise standard deviation 3. BER columns are percentages.
| Image / step | PSNR dB | JPEG BER | Noise BER |
|---|---|---|---|
| Airplane / 8 | 57.99 | 53.12% | 46.66% |
| Airplane / 16 | 52.15 | 45.24% | 19.90% |
| Airplane / 32 | 46.62 | 0.54% | 0.71% |
| Airplane / 64 | 40.72 | 0.00% | 0.00% |
| Boat / 8 | 57.97 | 54.03% | 48.66% |
| Boat / 16 | 52.29 | 44.41% | 21.34% |
| Boat / 32 | 46.69 | 0.49% | 1.12% |
| Boat / 64 | 40.86 | 0.00% | 0.00% |
We measured 231 incorrect bits for Airplane and 206 for Boat at step 8, caused by rounding the reconstructed pixels before any added attack. The embedded floating-point coefficients decoded without errors; clipping changed no decoding decisions. Steps 16, 32, 64 had zero incorrect bits in both un-attacked images. At step 32, JPEG quality 90 gave zero bit errors in both images; quality 30 gave 53.20% and 53.74%. Noise standard deviation 6 gave 18.68% and 19.24%, respectively. The JPEG and noise charts hold the step size at 32.
We apply an orthonormal DCT, which preserves total squared error before pixel rounding. Our implementation embeds one bit in coefficient (2, 3) of each 8×8 block, counting indices from zero. The reference bits score BER; the original image is used for PSNR alone.
| Setting | Value |
|---|---|
| Random-generator starting values | Airplane 2001; Boat 2002 |
| Python | 3.11.15 |
| Preparation | Grayscale conversion; no resizing |
| DCT | Orthonormal; coefficient (2, 3) |
| Offsets | For each coefficient, d(0) is uniform on [-Delta/2, Delta/2); d(1) is shifted half a step and wrapped into the same interval. |
| Attacks | Grayscale JPEG; Gaussian noise with average zero |
Conditions and limits
The decoder shares the offsets, coefficient position, block alignment and step size. The authors’ capacity results depend on their channel models and asymptotic coding assumptions. Section IX identifies scaling, rotation, cropping and column replacement as further implementation challenges.
Our test uses grayscale images and uncoded messages. Reconstructed pixels were rounded to integers and clipped to the brightness range before saving and attacking them. We applied JPEG and additive noise separately. Resizing, rotation, cropping, print-and-scan processing, error correction, distortion compensation and targeted removal remain untested. PSNR describes pixel error rather than a human visibility judgment.
Implementation details
The same message, offsets as fractions of the step size, and noise pattern were reused across step sizes for each image. Noise samples were independent before pixel rounding and clipping. The image implementation uses ordinary dither modulation without error-correction coding or distortion compensation.
References
- Brian Chen and Gregory W. Wornell. “Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding.” IEEE Transactions on Information Theory, 47(4), 1423-1443, May 2001. DOI: 10.1109/18.923725. Full text.
- USC Signal and Image Processing Institute. The USC-SIPI Image Database, Miscellaneous volume. Airplane, 4.2.05 and Boat, boat.512.
- Our re-implementation code and numeric results: GitHub, chen-2001-qim.