The present invention relates to a method for embedding a digital watermark into a halftone image comprised of clusters of halftone dots, which are referred to as geometric primitives. This method embeds a watermark image signal including an array of multilevel per pixel delta values by increasing or decreasing the size of a corresponding cluster of halftone dots. In particular, each delta value represents a change in luminance in one implementation, but this delta value could correspond to other color planes of a monotone or color halftone image. The watermark embedder subtly changes the halftone primitives by toggling boundary pixels on or off in a manner that grows or shrinks the primitive.