An electronic image into which an electronic watermark is to be embedded is divided into a plurality of image regions spatially, and pixels each having a property of being difficult to visually recognize a variation in a pixel value are extracted as adaptive pixels from each of the plurality of image regions. A variation between the pixel values of the adaptive pixels in one of the plurality of image regions and those of the adaptive pixels in an adjacent one of the plurality of image regions is produced, and the pixel values of the adaptive pixels of the plurality of image regions are varied in a time direction according to the value of an embedded bit set of the electronic watermark. An electronic-watermark-embedded image is then generated by making the variation in the pixel values of the adaptive pixels vary step by step at a boundary between the two of the plurality of image regions and/or in the time direction so that the variation makes a slow transition.