1. An image processing apparatus, which has embedding means for embedding information in image information, comprising: obtaining means for obtaining distribution information of pixel values by scanning the image information before the information is embedded by the embedding means; and detection means for detecting an information size, that can be embedded by the embedding means, on the basis of the obtained distribution information of pixel values.