1. A system comprising: a memory; a processor coupled to the memory; a watermark encoder executed by the processor and adapted to receive as input at least one video and at least one watermark, and to embed the watermark into the video, wherein the watermark encoder is adapted to perform a complexity analysis on a per-pixel basis on at least one region of the video, the complexity analysis based on a statistical video model that provides entropy rates in a direct current sub-band portion of the video; the watermark encoder adapted to partition the video into one or more scenes having one or more corresponding scene-cuts; the watermark encoder adapted to select one or more regions of the video to embed the watermark, wherein a region is randomly selected in time without the region overlapping any scene-cuts in the video; the watermark encoder adapted to embed the watermark into the video by using a two-dimensional discrete wavelet transform along spatial axes; the watermark encoder adapted to populate side information related to a region of the video, wherein the side information comprises a two-dimensional hash of a randomly selected frame within the video and data representing a motion field of a pixel in the video; and a watermark decoder executed by the processor and adapted to receive a watermarked video and to extract the watermark therefrom, wherein the watermark decoder locates the one or more regions of the video selected by the watermark encoder.