I would create a one-minute watermark video looped by a watermark moving every 20 seconds, then use an overlay filter to overlay this video on the original video.
Here is the image loop: http://ffmpeg.org/trac/ffmpeg/wiki/Create%20a%20video%20slideshow%20from%20images
And a watermark: http://www.idude.net/index.php/how-to-watermark-a-video-using-ffmpeg/
You can even repeat the process for a video watermark until it is the same length as the original video. I have not tested my theory, but you could tell us if it works.
edit, I went home and tested my theory, here is the Windows batch file:
setlocal rem create blank movie rem I created 4 transparent PNG the same size as my final movie using FotografixPortable rem after many failures with MSPaint... I should have known... rem add water mark to blank movie (bottom right) ffmpeg -loop 1 -i wm1.png -t 20 -vcodec png -pix_fmt rgba out-wm1.mov rem add water mark to blank movie (top right) ffmpeg -loop 1 -i wm2.png -t 20 -vcodec png -pix_fmt rgba out-wm2.mov rem add water mark to blank movie (bottom left) ffmpeg -loop 1 -i wm3.png -t 20 -vcodec png -pix_fmt rgba out-wm3.mov rem add water mark to blank movie (top left) ffmpeg -loop 1 -i wm4.png -t 20 -vcodec png -pix_fmt rgba out-wm4.mov rem put (concat) them all together into one video rem I use filter_complex because we need to maintain the transparency in the video ffmpeg -i out-wm1.mov -i out-wm2.mov -i out-wm3.mov -i out-wm4.mov -filter_complex "[0:0] [1:0] [2:0] [3:0] concat=n=4:v=1:a=0 [v]" -map "[v]" -y -vcodec png -pix_fmt rgba -q 0 all-wm.mov rem finally overlay the 1:20 watermark video onto the original movie ffmpeg -i "Ted (2012) Unrated.mkv" -i all-wm.mov -filter_complex overlay -shortest -y -q 0 ted.avi
Of course, this is not "random", but you can make your overlay movie any length of patterns and separate time stamps so that they seem random in the final output.
Isaac source share