An input image is divided into local regions, each of which is formed by a macro block. An embedment intensity is determined for each of the local regions by using a calculated characteristic amount and a compression bit rate. Digital watermarks are embedded at the determined embedment intensity into the input image at each of the local regions thereof. The input image is encoded, thereby providing a compressed bit stream that has the digital watermarks embedded therein.