1. A method for embedding a digital message into a digital representation of a perceptual object having a perceptual smoothness, comprising: defining a first portion of the perceptual object, having a property that it is (a) losslessly compressible and (b) can be replaced in the perceptual object with non-perceptual data to produce a perceptual object having a corresponding perceptual smoothness, while preserving a perceptual quality of the perceptual object; defining a second portion of the perceptual object, having a property that it is at least one of (a) not losslessly compressible and (b) cannot be replaced in the perceptual object with non-perceptual data to produce a perceptual object having a corresponding perceptual smoothness, while preserving a perceptual quality of the perceptual object; modifying the perceptual object, to substantially maintain the second portion and replace the first portion with non-perceptual data comprising at least a representation of the first portion, the digital message, and information for extracting the perceptual object and digital message from the modified perceptual object, wherein at least the first portion is losslessly compressed, and the modified perceptual object has a perceptual smoothness corresponding to a perceptual smoothness of the perceptual object.