The present invention relate generally to digital watermarking and data hiding. One claim recites an apparatus comprising: electronic memory for storing first color data and second color data, the first color data and the second color data represent data from a color image signal or color video signal, and a digital watermark signal, the digital watermark signal serving to facilitate detection of a watermark message; means for separating the digital watermark signal into first frequency components and second frequency components; means for modifying the first color data by hiding the first frequency components therein; and means for modifying the second color data by hiding the second frequency components therein. Of course, other combinations and claims are provided too.