A document image undergoes document analysis to obtain circumscribing rectangles of characters (S601), and two distances between non-neighboring circumscribing rectangles from the head of the document are respectively calculated as d1 and d2 (S603). If information to be embedded is 1, one or a combination of a process for changing a parameter associated with the size of a circumscribing rectangle and a process for changing a parameter associated with the position of a circumscribing rectangle is executed to satisfy d1>d2 (S605). If information to be embedded is 0, one or a combination of the above two parameter change processes is executed to satisfy d1