Aspects of the invention relate generally to steganography, data hiding and/or digital watermarking for video and other media signals. One claim recites a method including: obtaining a media signal comprising a message steganographically embedded therein; obtaining information obtained from the media signal; adjusting a message detection process with reference to the information; and detecting the message from the media signal according to the adjusted message detection process. Of course, other combinations are provided as well.