A watermarked image generator includes a watermark data source that inputs watermark data to a watermark embedding device. The watermark embedding device halftones the input image to generate the output image made of 22 binary patterns, the 22 binary patterns forming the watermarks embedded in the output image. The watermark embedding device includes a tri-level error diffusion generator that performs tri-level error diffusion on the input image by halftoning the input image into black, white and 50% gray. A plurality of halftoning circuits successively replace each pixel of the halftoned input image with one of a plurality of the 22 binary patterns. The one of the plurality of 22 binary patterns corresponds to at least one respective bit of the watermark data when a pixel of the halftoned image data is 50% gray. The watermark data can be segmentation map data of the input image.