The present disclosure relates generally to embedding auxiliary data and data hiding. One claim recites a method including: receiving data representing a media signal; using a programmed electronic processor, calculating perceptibility characteristics of the media signal, in which the perceptibility characteristics include contrast; using a programmed electronic processor, calculating a non-linear contrast to gain mapping using the perceptibility characteristics; using a programmed electronic processor, embedding an auxiliary signal in the media signal with reference to the non-linear contrast to gain mapping. Other claims and combinations are also provided.