Encoding information is assigned to each block according to a position of the block in an image of the color image data. An image analyzing unit analyzes the block and outputs a feature value. A block determining unit determines whether the block is an embedding-possible block based on the feature value and demarcates a watermark embedding area in the embedding-possible block. An embedding unit embeds the watermark information by deforming the watermark embedding area according to a pattern that represents the watermark information and replacing a pixel in the watermark embedding area with another pixel near the pixel to be replaced.