This patent document relates generally to steganography and digital watermarking. One claim recites, in a watermark encoder, a method of encoding auxiliary information in an image or video comprising: using a programmed electronic processor, computing a change in an attribute of an image or video sample to encode auxiliary information in the image or video; and changing color values of the image or video sample to effect the change in the attribute, in which changes to color values are determined based at least in part on both: i) visibility of the changes, and ii) anticipated watermark detection. Of course, other claims are provided too.