A method of embedding watermark data in a two-color image includes assessing the suitability of each of several candidate pixels to embed a bit of watermark data. Candidate pixels for which one pixel directly above, directly below, and immediately to the left and right of the candidate pixel have different colors, are identified. In one embodiment, only a single candidate pixel in each 2.times.2 block is identified. Suitability of each candidate pixel may be determined based on a relationship of coefficients computed from a binary wavelet or binary lifting transform formed from the image. Data is embedded by inverting suitable pixels. A recipient of the image may assess which blocks contain watermark data, by assessing the suitability of each 2.times.2 block in the image to embed data and extract data without further information about the data's location.