A device and method for embedding plural kinds of additional information or multiple bits of additional information into one picture is provided. A region information generating step generates region information to specify at least two regions in the real picture spatial or frequency space corresponding to the picture data, a coefficient sequence generating step sets at least two coefficient sequences, which are different from each other, a watermark pattern generating step allocates the coefficient sequences to each divided region to generate watermark patterns, and an embedding step embeds digital watermark information by changing the picture data using the watermark patterns.