An electronic watermark embedding apparatus for embedding watermark information as digital information into a document image includes a background eliminating unit that determines whether pixels on an input image are pixels composing a background image and eliminates the pixels determined as the pixels composing the background image from the input image, and a watermark embedding unit that embeds a watermark into a background eliminated image from which the background is eliminated by the background eliminating unit so as to form a watermark image. A readable watermark can be embedded into a multi-valued image including a halftone/gradation portion on the background of the input image.