System and methodologies are provided herein for low-distortion image watermarking. Parity relationships between multiple pixels and/or regions of an image can be leveraged as described herein to reduce the amount of toggling required to embed a watermark in an image, thereby increasing watermark efficiency and reducing visual artifacts introduced in a watermarked image. Various algorithms for leveraging parity relationships are described herein, including a Block-Overlapping Parity Check (BOPC) algorithm, a Champagne Pyramid Parity Check (CPPC) algorithm, and a Tree-Based Parity Check (TBPC) algorithm.