This patent application is generally related to watermarking and steganography. One claim recites a method of transmarking an audio or video signal previously embedded with a first digital watermark using a first digital watermark embedding method. The method includes: utilizing a programmed electronic processor, decoding the first digital watermark from the audio or video signal, in which the decoding determines relationships or values associated with local masking opportunities of the media signal; converting the audio or video signal into a different form; and utilizing a programmed electronic processor, embedding decoded message information from the first digital watermark into a second digital watermark in the different form such that the second digital watermark is adapted to robustness or perceptibility parameters associated with the different form. Of course, other combinations and claims are provided as well.