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 lowest number of macro-block dependencies; and embedding a watermark in macro-blocks selected from the set of macro-blocks having the lowest number of macro-block dependencies, wherein the number of macro-block dependencies associated with a given macro-block corresponds to a number of neighboring macro-blocks referenced during inter-frame and intra-frame prediction of the given macro-block.