An electronic watermark embedding device that embeds a graphic pattern representing information in image data includes a signaling feature period changing unit configured to change a period of signaling feature of a graphic pattern, a graphic pattern embedding unit configured to embed the graphic pattern in the image data as a period of the signaling feature changed by the signaling feature period changing unit, and an embedment region detecting unit configured to detect an embedding position where the graphic pattern is embedded from a region of the image data other than a background, whereby the signaling feature period changing unit changes the period of the signaling feature while maintaining the signaling feature when the image data undergo image enlargement or reduction processing, and the graphic pattern embedding unit embeds the graphic pattern in the embedding position on the region of the image data other than the background.