An intended image data structure is assumed to have a color information storing region and a pixel information storing region as its components. First, consider that the color information storing region within the image data structure is divided into a plurality of subregions, and a corresponding bit value is defined for each of the subregions. Next, an index number stored for each of pixels within the pixel information storing region is changed to an index number belonging to a subregion corresponding to a bit value of information to be embedded. In this way, one bit or more of information can be embedded for each pixel. Thus, a large amount of information can be embedded into a small-size image composed of simple shapes and having a small number of colors without degrading the image quality, and the information can be extracted from the image in which it has been embedded.