Methods, devices and computer program products allow embedding and detection of watermarks into and from a multimedia content. One watermark embedding method includes selecting a content segment that lacks inherent features for embedding of watermarks without producing perceptible artifacts, and obtaining a first dither pattern corresponding to a first watermark symbol of a watermark symbol alphabet, where each symbol is associated with a particular dither pattern. Further, each particular dither pattern, upon combination with the multimedia content segment that lacks inherent features, produces a composite content segment without perceptible artifacts. By combining the first dither pattern with the multimedia content segment that lacks inherent features, a first composite content segment with the first embedded watermark symbol is produced. The detection of watermarks messages can be carried out quickly by examining a small portions of the multimedia because even the featureless content segments include embedded watermarks.