pngnudge

The pngnudge algorithm was an accidential discovery. While failing at the pixeltweek denoising filter I found that it had the interesting side-effect of making some images considerably more compressible for PNG while producing (usually) minimal visual alteration. With some further refinement I was able to sacrifice noise removal ability and thus the visual alteration while retaining the compression optimisation in a reduced form.

The algorithm used is very simple - it's nothing more than a form of mode filter limited by a threshhold mask. The masking guarantees that no pixel is altered in color value by more than a defined distance (In RGB space) - anything less than around eight or so is imperceptable. The mode filter also has the interesting property of guaranteeing the output image palette is a subset (Though not a proper subset) of the input image palette - a factor that contributes to the compressibility and also prevents the introduction of fringe artifacts.

Essentially, the filter works by altering the boundries between quantitisation bands in a manner that gives them a more predictable structure. This is an emergent property - nothing in the filter explicitly operates on regions or boundries. It has a similar effect on JPEG compression artifacts - not directly removing them, but reshaping them in very slight ways to improve compressibility to PNG.

I have prepared some demonstration images. The filter in current form operates only upon 24-bit .BMP files - all PNGs were produced using the ImageMagick convert utility on default settings.

ImageDescriptionBeforeAfterRatio
A very simple cartoon image.53896506970.940644945821582
A more detailed cartoon image, after lossy video (h264) compression.4356573609120.828431541327237
A photograph.195869019534640.997331890191914
A more detailed cartoon.6288455493170.873533223608361
A scientific diagram, one which has never been lossy compressed.53860469690.87205718529521
Gradients and lots of pixel-level detail that must be preserved.2048911754830.856470025525767
Tux!39067388960.995622904241431
The ultimate gradient image.901689950.997670807453416
Two-color printable image.60283479550.795497901564288