Systems and methods are described that apply a watermark to data, such as data representing an image. In one implementation, the complexity of the image is measured. A quantization step size is calculated, based in part on the measured complexity of the image. A watermark or message is embedded into the image using the quantization step sizes derived for each coefficient of interest. In a further implementation, a mark decoding system is configured to extract the embedded message from the image data.