A method for synchronization of a digital watermark generates a digital watermark based on feature extraction and a key generator. The synchronization method is adapted for both temporal and spatial synchronization. Statistical features of the watermarked signal along with key generators are used to compute keys used to detect embedded digital watermarks that vary over time or space. For spatial synchronization, spatial redundancy is used to detect geometric distortion of a signal in which the watermark is embedded using an autocorrelation method to detect peaks caused by the redundancy of the watermark structure. These peaks are then analyzed with a histogram method to detect rotation and scaling of the host media signal. The spatial synchronization process is applied to watermarks for both intra-coded frames of video (I-frames) as well as still images.