A method and a carrier medium instructing a processor to execute a method. The method includes accepting a compressed video stream compressed by a compression method that uses macroblocks of possibly different macroblock types for each frame predictive encoding frames. The method further includes identifying a sequence of frames that are substantially visually indistinguishable and that include a predictively encoded frame and the at least one reference frame of the predictively encoded frame. The method further includes creating an ordered set of macroblocks, with the macroblock types of different macroblocks in the ordered set used to encode digital watermark information. The method further includes replacing the predictively encoded frame of the identified sequence with a newly-encoded predictively encoded replacement frame that contains the created ordered set of macroblocks, including the encoded watermarking information.