In one embodiment, a watermark is embedded in a sequence of video frames, for each one of the video frames, a set of N rectangular patches, two palettes of pixel values in a selected color space, such that the two palettes are denoted as P0 and P1, and P0≠P1, and in each one of the N patches a processor which chooses one of P0 and P1 according to a value of a payload bit to be encoded, a calculator which calculates one of a variance of pixel values in the frame, and edginess for the pixel values in the frame, thereby determining a calculated value, and a processor which determines if the calculated value is beneath a given threshold value, if the calculated value is beneath the given threshold value the processor is operative to calculate a function of the pixel values, the closest value to a result of the calculation of the function in the chosen palette is chosen, and a replacer which replaces the pixel values within the patch with the chosen closest value. Related systems, apparatus and methods are also described.