In order to embed a watermark into a binary document image, some subset of image pixels needs to be modified. This modification will cause a document image distortion. Careful selection of image pixels can make distortion appear less visible. We propose a new binary document image pixel scoring method, the Structural Distortion Measure, whose objective is to identify image pixels whose modification, as part of a watermark embedding process, will minimize document image visible distortion.