Multi-grid compression

This is a fairly straightforward compression method of my own invention; I thought of it when considering how to animate Newton sets. The Newton set images have quite large monochrome regions; the compression method is essentially useless for images without this property.

At the moment, it has three other requirements: the image must be a power of two pixels on a side, it must be in eight-bit paletted mode, and there must be at least one unused colour in the palette. All of these could easily be relaxed if I started to find them oppressive, though I suspect images which use more than 256 colours might well lack the large monochrome regions.

The algorithm is trivial. We start off with a square region [0, 0, sz], centred at the top left of the image and the size of the image. To compress a region, we check whether all the pixels in it are monochrome. If so, we output the colour. If not, we output a non-monochrome token (using the unused colour in the palette), and follow it by the compressed version of each of four sub-regions of the image:

void SSCO(MonoPyramid& mc, int x, int y, int rsz, FILE* f) 
{
  int t = mc.IsMono(x, y, rsz);
  if (t == -1)
  {
    fputc(255, f);
    SSCO(mc, x, y, rsz/2, f);
    SSCO(mc, x+rsz/2, y, rsz/2, f);
    SSCO(mc, x+rsz/2, y+rsz/2, rsz/2, f);
    SSCO(mc, x, y+rsz/2, rsz/2, f);
  }
  else 
    fputc(t, f);
}

Loading is equally straightforward (though slightly obscured because SSCO writes to a file and leaves stdio to handle the file pointer, and LLCO reads from memory and has to advance the pointer itself):

unsigned char* LLCO(unsigned char* comp, unsigned char* out, int x, int y, int opitch, int osz)
{
  if (*comp == 255)
  {
    // Not monochrome; split

    unsigned char* k1 = LLCO(comp+1, out, x, y, opitch, osz/2);
    k1 = LLCO(k1, out, x+osz/2, y, opitch, osz/2);
    k1 = LLCO(k1, out, x+osz/2, y+osz/2, opitch, osz/2);
    k1 = LLCO(k1, out, x, y+osz/2, opitch, osz/2);
    return k1;
  }
  else
  {
    // Monochrome: fill
    unsigned char chrome = *comp;

    for (int yy=y; yy<y+osz; yy++)
      memset(out + xx + yy*opitch, chrome, osz);
    return comp+1;
  }
}

Monochromaticity pyramids

The algorithm as described above spends quite a lot of time checking redundantly whether regions are monochrome. To speed it up, I use a data structure inspired by the MIP-mapping technique from texture mapping, which I call a monochromaticity pyramid.

At the top level of the pyramid is the original image. At each level down, we consider the image at the previous level as made up of 2x2 blocks: if they are monochrome, we record the colour, and if not, we record a special token. See the diagram below (drawn with dia; the source is here and I'd appreciate any comments about my dia technique):

To answer a query about a region, you need only check one pixel, in the image from the pyramid layer where the size of the pixels is the size of the queried region.