An apparatus for embedding a digital watermark in a document image detects circumscribing outer shapes of characters in the document image and sets a plurality of reference lines that extend in the column direction and are spaced apart in the row direction by a basic pitch. The outer shapes include a first outer shape, a second outer shape that neighbors the first outer shape, and a third outer shape that neighbors the second outer shape, and the reference lines include a first reference line located between the first outer shape and the second outer shape, and a second reference line located between the second outer shape and the third outer shape. Control is performed for at least one of the second and third outer shapes so that a distance between the first reference line and an edge of the second outer shape is different from a distance between the second reference line and an edge of the third outer shape, in accordance with digital watermark information to be embedded.