1. A method of watermarking encoded video frames, the method comprising: electronically receiving a bitstream comprising a plurality of encoded video frames, each video frame being divided into a plurality of macro-blocks; determining macro-block dependencies based on prediction information in the received bitstream; determining a set of macro-blocks having a minimal number of macro-block dependencies; and embedding a watermark in a plurality of macro-blocks selected from the set of macro-blocks having the minimal number of macro-block dependencies.