1. An information processing apparatus which embeds information in each character in an original document, the apparatus comprising: extraction unit for extracting circumscribed rectangles of characters from the original document; selection unit for selecting, based on a predetermined condition, a character in which information is to be embedded, from the characters included in the respective circumscribed rectangles; information embedding unit for embedding information in a character selected by the selection unit as the character in which information is to be embedded; character generation unit for generating a character not selected by the selection unit at a lower pixel density per unit area than a pixel density of the character in which the information embedding unit embeds the information; and output unit for outputting the original document processed by the information embedding unit and the character generation unit.