A method of detecting an embedded watermark, the method executed at a detection device, the method comprising: receiving definitions of two palettes of pixel values in a selected color space, such that the two palettes are denoted as P0 and P1, and P0≠ P1 where each one of P0 and P1 were used to encode different values of a payload bit; calculating at a processor one of variance and edge detection for pixel values in a candidate patch (620, 630, 640, 650), the candidate patch (620, 630, 640, 650) being a portion of a video frame which might comprise a watermark; if the one of variance and edge detection for the candidate patch (620, 630, 640, 650) is below a given threshold value, then: determining a value for pixel values in the candidate patch (620, 630, 640, 650) by operating on the pixel values of the candidate patch (620, 630, 640, 650) in the selected color space using the same function as a function that had been used in embedding the watermark; determining whether the determined value is a closer distance in the selected color space to a pixel value that is a member of palette P0 or to a pixel value that is a member of palette P1; and setting the value of the palette having the pixel value as a member to which the determined value is a closer distance to be an output value for the candidate patch (620, 630, 640, 650); if the one of variance and edge detection for the candidate patch (620, 630, 640, 650) is above the given threshold value, then ignoring the candidate patch (620, 630, 640, 650); applying a majority function operation to the output values of all the candidate patches (620, 630, 640, 650) which were not ignored, and using an output bit of the majority function as a payload bit for the frame; and recovering the bit of the embedded watermark by applying any error correcting methods on the payload bit output in the step of applying the majority function. receiving definitions of two palettes of pixel values in a selected color space, such that the two palettes are denoted as P0 and P1, and P0≠ P1 where each one of P0 and P1 were used to encode different values of a payload bit; calculating at a processor one of variance and edge detection for pixel values in a candidate patch (620, 630, 640, 650), the candidate patch (620, 630, 640, 650) being a portion of a video frame which might comprise a watermark; if the one of variance and edge detection for the candidate patch (620, 630, 640, 650) is below a given threshold value, then: determining a value for pixel values in the candidate patch (620, 630, 640, 650) by operating on the pixel values of the candidate patch (620, 630, 640, 650) in the selected color space using the same function as a function that had been used in embedding the watermark; determining whether the determined value is a closer distance in the selected color space to a pixel value that is a member of palette P0 or to a pixel value that is a member of palette P1; and setting the value of the palette having the pixel value as a member to which the determined value is a closer distance to be an output value for the candidate patch (620, 630, 640, 650); determining a value for pixel values in the candidate patch (620, 630, 640, 650) by operating on the pixel values of the candidate patch (620, 630, 640, 650) in the selected color space using the same function as a function that had been used in embedding the watermark; determining whether the determined value is a closer distance in the selected color space to a pixel value that is a member of palette P0 or to a pixel value that is a member of palette P1; and setting the value of the palette having the pixel value as a member to which the determined value is a closer distance to be an output value for the candidate patch (620, 630, 640, 650); if the one of variance and edge detection for the candidate patch (620, 630, 640, 650) is above the given threshold value, then ignoring the candidate patch (620, 630, 640, 650); applying a majority function operation to the output values of all the candidate patches (620, 630, 640, 650) which were not ignored, and using an output bit of the majority function as a payload bit for the frame; and recovering the bit of the embedded watermark by applying any error correcting methods on the payload bit output in the step of applying the majority function.