A method of embedding a digital watermark into a halftone image. The method redundantly encodes a multi-bit message, and transforms the encoded message to a multilevel per pixel watermark image. It then derives halftone thresholds from the multilevel per pixel watermark image. These thresholds are then used to convert target images into watermarked halftone images. The multilevel pixels in the target image are used to select corresponding halftone thresholds from the halftone thresholds derived from the watermark image. The selected thresholds are applied to corresponding multilevel pixels in the watermark image to create the watermarked halftone image of the target image. A method of measuring digital watermark strength. In this method, a watermarked signal is processed to extract estimates of error correction encoded bits embedded into the watermarked signal. Then, the error correction encoded bits are decoded to compute a message payload. The message payload is re-encoded to compute error correction encoded bits. A measure of watermark strength is computed from the error correction encoded bits and the estimates of error correction encoded bits. In particular, in one implementation the soft bit estimates decoded from the watermarked signal are multiplied by corresponding re-computed error correction encoded bits and summed to get a measure of the watermark signal strength. This measurement may be compared with a threshold to detect tampering with the watermarked signal, such as compression, scanning and re-printing, photo-copying, etc. For printing applications, the embedded digital watermark may be used to carry printer information that is later decoded by a watermark detector and used to examine a digital scan of a printed object and determine whether the printed object is authentic.