Blind error-free detection of transform-domain watermarks

In this paper we propose a new blind, error-free detection algorithm for watermarking in transform domains. The detection scheme uses linear decoding techniques from the recent theory of Compressive Sensing (CS), whose central idea is that a small number of non-adaptive linear projections of a sparse signal are sufficient for error-free reconstruction of the original signal. We use the fact that natural images are approximately sparse in the DCT or wavelet basis; with an extra step of sparsification or scaling of the coefficients we can decode both the original image and watermark with zero error, despite not knowing the host image. Besides being error-free, our proposed detection algorithm has low complexity compared to other blind algorithms. It can be extended to any transform-domain watermarking method, and also be used to watermark already compressed images.