In an embedding technique of an invisible or visible digital watermark information, it is a main object to provide a technique which can reconstruct an original image and avoid an increase of the whole image data due to holding of key information or the like. To accomplish this object, an image processing apparatus of the invention is constructed by, an input unit for inputting image data showing an original image, a compressing unit for compressing at least a part of the image data, and an embedding unit for embedding compression data obtained by the compressing unit into the image data so that it is difficult to be identified by the human eyes by converting a part of the image data.