The presently claimed invention relates generally to digital watermarking of data, e.g., representing video or audio. One claim recites a method including: obtaining data representing video or audio; using a multi-purpose electronic processor programmed for: transforming the data into a transform domain, analyzing the transformed data to identify a plurality of transform coefficients according to predetermined criteria, and altering the identified plurality of transform coefficients to carry a digital watermark; and analyzing the data to determine a baseline state for the digital watermark. Of course, other combinations and claims are provided too.