In this paper, a watermarking scheme, called Majority-Parity-Guided Error-Diffused Block Truncation Coding (MPG-EDBTC), is proposed to achieve with high image quality and embedded capacity. The main problem of traditional BTC is its poor quality over configurations of high compression ratio. To overcome such problem, the extreme pixel values are employed to substitute both high and low means. The quantized error is also compensated by adjusting the neighboring pixels. With these strategies, the image quality and processing efficiency are improved. Moreover, the watermark is embedded by evaluating the parity value in a pre-defined Parity-Check Region (PCR). As seen in the experimental results, the proposed scheme can provide good robustness, image quality, and processing efficiency. Finally, the proposed MPG-EDBTC is extended to embed multiple watermarks and achieves excellent image quality, robustness, and capacity as well. Nowadays, most multimedia is stored in compressed format. It is more appropriate to embed information such as watermarks in compressed domain. The proposed method has been proved to solve effectively the inherent problems in traditional BTC, and provide excellent performance in watermark embedding.