The present invention relate generally to digital watermarking and data hiding. One claim recites a method including: obtaining first 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; obtaining a digital watermark pattern, the pattern aiding detection of a watermark message; separating the digital watermark pattern into first frequency components and second frequency components; utilizing a programmed electronic processor or electronic processing circuitry, modifying the first color data by hiding the first frequency components therein; and utilizing a programmed electronic processor or electronic processing circuitry, modifying the second color data by hiding the second frequency components therein. Of course, other combinations and claims are provided too.