A color conversion module 42 carries out color conversion of original color image data G.sub.rgb from the RGB color system into the CMYK color system to obtain color-converted original color image data G.sub.cmyk (step S104). A DCT module 44 applies DCT (discrete cosine transform) over the whole color-converted original color image data G.sub.cmyk to generate DCT coefficients D.sub.cmyk (step S106). An embedding module 46 embeds the watermark information s into the components C, M, Y, and K of the DCT coefficients D.sub.cmyk (step S108). An IDCT module 48 applies IDCT (inverse discrete cosine transform) onto DCT coefficients D'.sub.cmyk with the watermark information s embedded therein to generate embedding-processed color image data G'.sub.cmyk (step S110). The color conversion module 42 carries out color conversion of the embedding-processed color image data G'.sub.cmyk from the CMYK color system into the RGB color system to obtain embedding-processed color image data G'.sub.rgb (step S112). This arrangement does not require any correction of the position or the shape of image blocks in the process of extracting the embedded watermark information.