This patent document relates generally to steganography and digital watermarking. One claim recites, a method of encoding auxiliary information in an image or video. The method includes: determining a watermark tweak for an attribute of an image or video sample to encode auxiliary information in the image or video; and altering color values of the image or video sample to effect the watermark tweak, said altering alters color values based at least in part on both: i) visibility of color value alterations, and ii) anticipated watermark detection. Of course, other claims are provided too.