A watermarked halftone image is generated from a continuous tone image by performing error diffusion halftoning on the continuous tone image while adding a watermark to the halftone image during the halftoning. A location of the watermark in the halftone image may be based on prediction criteria. Error caused by adding the watermark may be diffused into the halftone image.