Using correlated stochastic screens, time stamps, text messages, logos and other variable data can be incorporated into printed halftone images in real-time as invisible watermarks. A reference stochastic screen, which is suitable for halftoning the input image, is applied to the grayscale input in locations that lie outside of the watermark. A multi-partitioned watermark halftone screen, which has at least one partition with threshold values that are positively correlated (e.g., identical to) those of the reference stochastic screen and one partition with threshold values that are negatively correlated (e.g., conjugated with) those of the reference stochastic screen, is applied to the grayscale input in locations that are to incorporate the watermark.