1. An image processing apparatus that embeds watermark information in color image data that has been divided into a plurality of blocks, each of which includes a plurality of pixels and to each of which encoding information is assigned according to a position of a first block of the plurality of blocks in an image of the color image data, the image processing apparatus comprising: an image analyzing unit configured to output a feature value of the first block based on an analysis of image data of the first block; a block determining unit configured to determine whether the first block is an embedding-possible block in which the watermark information can be embedded based on the feature value of the first block and to demarcate, for the embedding-possible block, a watermark embedding area that is an area in which the watermark information is to be embedded in the embedding-possible block; and an embedding unit configured to embed the watermark information by deforming the watermark embedding area of the embedding-possible block 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.