We propose a new method to compress error-diffused bilevel images with resolution scalability. This method is a combination of inverse halftoning and rehalftoning. For the inverse halftoning, we combine 2×2 dots into a single pixel of a resolution-reduced image, where each pixel has a multilevel value of 0, 1, 2, 3, and 4. After the inverse halftoning, the resolution-reduced multilevel image is halftoned by using an error diffusion algorithm. Thus, the resolution of the error-diffused bilevel images can be reduced by repetition of the inverse halftoning and rehalftoning processes. After reducing the image size, we encode an error-diffused bilevel image progressively from the lowest resolution image to the highest resolution image. To encode higher resolution images, we use the information in the previously coded lower resolution image. Though the compression ratios of the proposed algorithm are similar to those of progressive Joint Bilevel Image Processing Group (JBIG), the image quality of the resolution-reduced image from the proposed algorithm is much better than that from the progressive JBIG.