An efficient algorithm for informed embedding of dirty-paper trellis codes for watermarking

Dirty paper trellis codes are a form of watermarking with side information. These codes have the advantage of being invariant to valuemetric scaling of the cover work. However, the original proposal requires a computational expensive second stage, informed embedding, to embed the chosen code into the cover Work. In this paper, we present a computational efficient algorithm for informed embedding. This is accomplished by recognizing that all possible code words are uniformly distributed on the surface of a high n-dimensional sphere. Each codeword is then contained within an (n - 1)-dimensional region which defines an n-dimensional cone with the centre of the sphere. This approximates the detection region. This is equivalent to the detection region for normalized correlation detection, for which there are known analytic methods to embed a watermark in a cover work. We use a previously described technique for embedding with a constant robustness. However, rather than moving the cover work to the closest Euclidean point on the defined surface, we find the point on the surface which has the smallest perceptual distortion. Experimental results on 2000 images demonstrate a 600-fold computational improvement together with an improved quality of embedding.