In publishing applications, it is advantageous to embed data in halftone images. The CPT scheme (Chen-Pan-Tseng, 2000) is a steganographic data hiding scheme that was proposed for binary images, e.g., facsimiles. The CPT scheme uses a secret key and weight matrix to protect the hidden data and can hide as many as $r={lfloor}{log}_2(m{ imes}n+1){ floor}$ bits of data in the image by changing at most 2 bits in the image. Our proposed scheme also uses a secret key to protect it from being compromised and a weight matrix to increase the data hiding rate. Our scheme improves the performance of the CPT scheme by using the simple principle of splitting each block into two parts. Our proposed scheme is called improved CPT (ICPT) and has a very high embedding capacity compared to previous schemes. Experimental results demonstrate that our proposed scheme generally has higher performance than previous schemes.