This invention can multiplex noise in 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, 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, a bit region where noise is to be multiplexed in the pixel of interest is specified on the basis of data in a region near the pixel of interest (S110). Bit information is reversibly changed in the specified bit region of the pixel of interest (S112, S114).