1. An image processing apparatus comprising: an inputting unit arranged to input a watermarked document image, wherein the watermarked document includes a first area where density value of pixel data of characters has been altered in order to embed predetermined information bits, and a second area different from the first area where density value of pixel data of characters has been altered in order to embed a watermark message; a generating unit arranged to generate, for each character image, a density histogram indicating a frequency of a density value of pixel data of each character image in the input document image; a first most frequent value obtaining unit arranged to obtain, for each character image in the first area, a most frequent value in the density histogram generated by the generating unit; a minimum value obtaining unit arranged to obtain the minimum most frequent value obtained by the first most frequent value obtaining unit for characters in which an information bit 1 is embedded; a maximum value obtaining unit arranged to obtain the maximum most frequent value obtained by the first most frequent value obtaining unit for characters in which an information bit 0 is embedded; a reference value obtaining unit arranged to obtain a reference frequency value by averaging the minimum frequency value obtained by the minimum value obtaining unit with the maximum frequency value obtained by the maximum value obtaining unit; a second most frequent value obtaining unit arranged to obtain, for each character in the second area, a most frequent value in the density histogram generated by the generating unit; a comparing unit arranged to compare, for each character image in the second area, the reference frequency value obtained by the reference value obtaining unit and the most frequent value obtained by the second most frequent value obtaining unit; and an extracting unit arranged to extract a watermark message embedded in each character image in the second area based on a result of the comparison by the comparing unit.