This invention can multiplex noise on multilevel image data to reversibly embed visible additional information with a noise-multiplexed distribution while maintaining the atmosphere of the multilevel image data subjected to embedding. For this purpose, in this invention, when noise is multiplexed on multilevel image data to embed visible additional information with a noise-multiplexed distribution, information representing whether or not to multiplex noise for each pixel is input as the additional information. Whether a pixel of interest in the multilevel image data is located at a position where noise is to be multiplexed is determined on the basis of the additional information (S106). When the pixel of interest is determined to be located at the position where noise is to be multiplexed, the second bit region where noise is to be multiplexed is specified on the basis of the first bit region in a bit configuration which constitutes the pixel of interest (S110). Bit information in the second bit region of the specified pixel of interest is changed (S112, S114).