This paper proposes a new method to embed watermark in binary images. The given binary image is partitioned into two level blocks, and the watermark will be embedded into the sub-blocks based on the parity of characteristic values. The method is very efficient especially when applied to those binary images whose black and white pixels are distributed approximately uniformly. The experimental results show that the method only requires fewer operations and it can embed more watermarks. Embedding two bits information in a 4*4 block needs to change only one and a half pixels on average.