Quantization index modulation: A class of provably good methods for digital watermarking and information embedding

We consider the problem of embedding one signal (e,g,, a digital watermark) , within another "host" Signal to form a third, "composite" signal. The emb edding is designed to achieve efficient tradeoffs among the three conflicti ng goals of maximizing information-embedding rate, minimizing distortion be tween the host signal and composite signal, and maximizing the robustness o f the embedding. We introduce new classes of embedding methods, termed quantization index mo dulation (QIM) and distortion-compensated QIM (DC-QIM), and develop conveni ent realizations in the form of what we refer to as dither modulation. Usin g deterministic models to evaluate digital watermarking methods, we show th at QIM is "provably good" against arbitrary bounded and fully informed atta cks, which arise in several copyright applications, and in particular, it a chieves provably better rate distortion-robustness tradeoffs than currently popular spread-spectrum and low-bit(s) modulation methods. Furthermore, we show that for some important classes of probabilistic models, DC-QIM is op timal (capacity-achieving) and regular QIM is near-optimal. These include b oth additive white Gaussian noise (AWGN) channels, which mag be good models for hybrid transmission applications such as digital audio broadcasting, a nd mean-square-error-constrained attack channels that model private-key wat ermarking applications.