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, noise is multiplexed on multilevel image data containing a luminance component as a main component, thereby embedding visible additional information with a noise-multiplexed distribution. At this time, 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 (S806). When the pixel of interest is determined to be located at the position where noise is to be multiplexed, an embedding amount to be added to the position of the pixel of interest is calculated on the basis of data of a region near the pixel of interest (S810), and is added (S812).