|

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:

  1. Optionally encode message bits with an error-correction code, adding redundancy.
  2. Divide the host into nonoverlapping blocks and assign a coded bit to each block.
  3. Construct paired offsets and a base quantizer for each block.
  4. 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.

A bit chooses a shifted grid Illustrative host x = 13.3, step Delta = 8, offsets d(0) = -2 and d(1) = 2. All number lines use the same scale. Circles mark the bit-zero grid at 2, 10, 18, 26; squares mark the bit-one grid at 6, 14, 22. Each grid has spacing 8, and the grids interleave 4 apart. Filled purple marks are the possible embedded values; a diamond marks the host. For bit zero, x plus d is 11.3, q gives 8, and subtracting d gives s = 10. For bit one, x plus d is 15.3, q gives 16, and s = 14. Send 14 and add 1.5, receiving y = 15.5. The nearest bit-one point is 14, distance 1.5; the nearest bit-zero point is 18, distance 2.5. The decoder reads bit 1. An amber bracket with open ends spans decision boundaries 12 and 16; disturbances strictly smaller than the quarter-step 2 preserve the bit. No rounding ties occur. The original host is not needed or restored. A bit chooses a shifted grid Illustrative host x = 13.3 Step Delta = 8 Offsets: d(0) = -2; d(1) = 2 Two grids, interleaved 4 apart bit 0 s = 10 bit 1 s = 14 x = 13.3 Round, then subtract the offset bit 0: q(11.3) = 8 s = 8 – (-2) = 10 bit 1: q(15.3) = 16 s = 16 – 2 = 14 Read after a small disturbance y = 14 + 1.5 = 15.5 18 14 y = 15.5 Quarter-step tolerance: < 2 Open ends are decision boundaries To bit 1: |15.5 – 14| = 1.5 To bit 0: |15.5 – 18| = 2.5 Nearest grid: bit 1
A bit chooses a shifted grid

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.

Figure 6: marked point s highlighted between the dashed decision boundaries

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.

Dither modulation embeds and decodes a coefficient Embedding adds a bit dependent offset, quantizes and subtracts it, while decoding chooses the nearest of the two shifted grids. Embed by rounding. Decode by grid distance. Embedding: the bit selects the dither offset. Decoding: use the same offsets and step size. q rounds to the base grid. d is the bit-dependent offset. The decoder uses the received value and grid settings. It does not need the original image. Input coefficient x Add bit offset x + d(bit) Round, then subtract q(x + d) – d Marked value s Received value y Try both shifted grids |y – q(y+d) + d| Choose closest grid minimum distance Read bit 0 or 1
Dither modulation embeds and decodes a coefficient (open full size)

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.

Figure 9: 4.3 dB low-rate limit highlighted

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

Figure 10: peak received-host quality gap highlighted

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.

Figure 11: STDM curve at error probability 10^-6 highlighted

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.

MethodDistortion 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.

SettingValue
Preparation512×512 grayscale
Blocks; payload8×8; 4,096 bits
Step sizes8, 16, 32, 64
JPEG qualities90, 70, 50, 30
Noise standard deviations1, 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.

Airplane original, watermarked image, and amplified difference at step size 32
Boat original, watermarked image, and amplified difference at step size 32
Airplane after each JPEG and noise attack, with PSNR and bit error rates
Boat after each JPEG and noise attack, with PSNR and bit error rates

The table pairs un-attacked PSNR with BER after JPEG quality 70 and noise standard deviation 3. BER columns are percentages.

Image / stepPSNR dBJPEG BERNoise BER
Airplane / 857.9953.12%46.66%
Airplane / 1652.1545.24%19.90%
Airplane / 3246.620.54%0.71%
Airplane / 6440.720.00%0.00%
Boat / 857.9754.03%48.66%
Boat / 1652.2944.41%21.34%
Boat / 3246.690.49%1.12%
Boat / 6440.860.00%0.00%
Embedding image quality: our measurements Un-attacked images. PSNR (dB) for Airplane and Boat. Embedding image quality: our measurements Airplane Boat Un-attacked images PSNR (dB) 0 20 40 60 8 16 32 64 Quantization step size
Embedding image quality: our measurements
JPEG bit errors: our measurements Step size 32. Bit error rate (%) for Airplane and Boat. JPEG bit errors: our measurements Airplane Boat Step size 32 Bit error rate (%) 0 20 40 60 30 50 70 90 JPEG quality setting
JPEG bit errors: our measurements
Noise bit errors: our measurements Step size 32; noise in brightness levels. Bit error rate (%) for Airplane and Boat. Noise bit errors: our measurements Airplane Boat Step size 32; noise in brightness levels Bit error rate (%) 0 5 10 15 20 25 0 1 3 6 Noise standard deviation
Noise bit errors: our measurements

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.

SettingValue
Random-generator starting valuesAirplane 2001; Boat 2002
Python3.11.15
PreparationGrayscale conversion; no resizing
DCTOrthonormal; coefficient (2, 3)
OffsetsFor each coefficient, d(0) is uniform on [-Delta/2, Delta/2); d(1) is shifted half a step and wrapped into the same interval.
AttacksGrayscale 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.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *