A method for performing recoverable image and video watermarking which survives the use of block-based image and video compression techniques. One or more of the lowest order bits of the first DCT coefficient (the “DC” coefficient) which is to be coded are used as a “data channel” by which information representing a recoverable watermark may be embedded into an image or into a video signal frame. Encoding is performed by replacing one or more low order bits of the luminance value of each pixel in a block with a number of bits of the watermark data, and decoding is performed by averaging one or more low order bits of the decoded luminance values of the pixels in a block to retrieve a corresponding number of bits of the watermark data.