Bitonal image compression and interlacing

[Karhunen]

Here is the discussion on why raster images should be interlaced for a slow connection: http://en.wikipedia.org/wiki/Interlacing_(bitmaps)

But I have had the experience that interlacing an image, either under LZW with GIF or Deflate with PNG seems to improve the compression.

I have attached a zip file of the files I was working with, apparently from wikimedia based on the filenames:

My question is, is the benefit from compression because interlacing "exposes" the self-similarity of the image, or is it because the interlacing imposes a sorting of the image elements that is easier to compress ?

I think it is the latter because this seems to work with a lot of line-art images that are drawn by a human. Anybody have an interesting test set of 1bpp images ?

[Piotr Tarsa]

Well, from counting theorem we have that if one algorithm compresses some files better than other algorithm, then it has to compress some files worse. So if interlacing usually worsens compression ration, then it should improve compression in rare cases.

I think, if you separate odd and even lines from the image to two separate images, then one will have a lot of white pixels and one will have a lot of black pixels. That would be a reson for improved compression.

[Matt Mahoney]

Right. I think interlacing would make compression worse for most images. In the maze image, the even and odd lines have obviously different statistics.