This invention can multiplex noise on an original image to reversibly embed visible additional information with a noise-multiplexed distribution, and can generate an image highly resistant to noise removal. For this purpose, when noise is multiplexed on multilevel image data to embed visible additional information with a noise-multiplexed distribution, information representing which of the first and second noise multiplexing processes is performed for each pixel is input as the additional information (S102). The position of a pixel of interest in the multilevel image data is determined on the basis of the additional information (S106). Either of the first noise addition processing (S108) and the second noise addition processing (S110) is performed on the basis of the determination result.