1. An electronic watermark embedding device that embeds a graphic pattern representing information in image data, the electronic watermark embedding device comprising: a signaling feature period changing unit configured to change a period of a 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 embeddable from a region of the image data other than a background, wherein the signaling feature period changing unit changes the period of the signaling feature of the graphic pattern 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.