Watermarking schemes are known that embed the watermark directly in the MPEG domain. A requirement for these algorithms is that the watermarked MPEG stream does not increase in size. Therefore, a bit rate controller allows a modification of a DCT coefficient only if such modification does not increase the stream size. It happens frequently that DCT coefficients are skipped because of this requirement. As a direct consequence, the watermark energy is smaller than desired and therefore the watermark is less robust. This invention exploits the fact that stuffing bits have often already been added to the stream by the MPEG encoder. The embedder is arranged to analyse the stream so as to find out how many stuffing bits there are at the end of the slice. The embedder can then embed the watermark immediately at the beginning of a slice. As a direct result, the watermark energy will increase and therefore the watermark will be more robust.