We propose a predictive coding algorithm for lossy compression of digital halftones produced by clustered-dot dithering. In our scheme, the predictor estimates the size and shape of each halftone dot (cluster) based on the characteristics of neighboring clusters. The prediction template depends on which portion, or sub-cell, of the dithering matrix produced the dot. Information loss is permitted through imperfect representation of the prediction residuals. For some clusters, no residual is transmitted at all, and for others, information about the spatial locations of bit errors is omitted. Specifying only the number of bit errors in the residual is enough to allow the decoder to form an excellent approximation to the original dot structure. We also propose a simple alternative to the ordinary Hamming distance for computing distortion in bi-level images. Experiments with 1024/spl times/1024 images, 8/spl times/8 dithering cells, and 600 dpi printing have shown that the coding algorithm maintains good image quality while achieving rates below 0.1 bits per pixel.