Structure-preserving properties of bilevel image compression

We discuss a new approach for lossy compression of bilevel images based on Markov random fields (MRFs). The goal is to preserve key structural information about the image, and then reconstruct the smoothest image that is consistent with this information. The image is compressed by losslessly coding the pixels in a square grid of lines and adding bits when needed to preserve structural information. The decoder uses the MRF model to reconstruct the interior of each block bounded by the grid, based on the pixels on its boundary, plus the extra bits provided for certain blocks. The idea is that, as long as the key structural information is preserved, then the smooth contours of the block having highest probability with respect to the MRF provides acceptable reconstructions. We propose and consider objective criteria for both encoding and evaluating the quality and structure preserving properties of the coded bilevel images. These include mean-squared error, MRF energy (smoothness), and connected components (topology). We show that overall, for comparable mean-squared error, the new approach provides perceptually superior reconstructions than existing lossy compression techniques at lower encoding rates.