Lossy DEFLATE, lossy PNG

[porneL]

Is anybody working on a lossy DEFLATE compressor?

I'm interested in developing lossy PNG compressor (although PNG is supposed to be lossless by design, it's possible to distort/discard image data while compressing to reduce file size).

I've tried to do it by degrading images "blindly" without feedback from deflate: https://github.com/pornel/mediancut-posterizer . It can reduce file size by 10-20% without noticeable distortion (and a little bit more if first treated with lossy RLE), but obviously much better compression could be achieved with "proper" lossy compression.

There's also http://meesoft.logicnet.dk/Analyzer/ that reduces PNGs by using X/Y filter on all rows and forcing as many zeros as possible (creating diagonal blur - http://allspark.net/cypherswipe/treetest.html), but I think it's also merely blind preprocessing rather than proper lossy compressor where distortion is only where beneficial, rather than everywhere upfront.

The only true lossy DEFLATE seems to be an unfinished experiment: http://membled.com/work/apps/lossy_png/ showing that even little distortion can halve the size. Has anybody continued/reimplemented something like that?

[thorfdbg]

I'm interested in developing lossy PNG compressor (although PNG is supposed to be lossless by design, it's possible to distort/discard image data while compressing to reduce file size).

Lossy data compression is an entirely different business. You cannot expect to take a medicre lossless compression like PNG and make it better by introducing loss. The problem is here that, for good lossy, the image should be represented in a domain that allows you to introduce almost invisible loss. Transformations like DCT or DWT do just that, but PNG doesn't have this. The same problem also applies for JPEG-LS: It is a very good lossless process, but as soon as you introduce loss, it becomes very visible as "stripes" on the image. Loss is no longer "confined" to small areas, but extends over the full image and then becomes easily observable.

[Sebastian W]

I am pretty sure, that I had a GUI-tool that did lossy PNG compression years ago. I think it was Adobe Photoshop in the "save for the web..." dialog. Version CS4 or CS5 maybe.

It had a slider to adjust the lossyness (0%-100% I think).
The loss I remember was to equalize pixels that were next to each other in a horizontal line and already close in color. A high loss value made pictures ugly, with long, horizontal lines, but very small loss was more acceptable to my eye than the reduction from true-color to paletted color (<=256 colors).

I guess, that tool didn't have the alternative filters of the PNG format in mind.

When we define two areas in an image, the main part and the not so important part, lossy DEFLATE makes sense to me. Lossy in the sense of producing zeros by making very similar pixels equal and lossy by allowing DEFLAT to find better matches that are not perfect but pretty close. You also might make dithering more compression friendly.

[porneL]

@thorfdbg: Definitely PNG is a poor base for a lossy format, but for better or worse, it's universally supported and widely used, so I'd rather make it less wasteful until something better replaces it.

@Sebastian W: Photoshop has lossy option for GIF. In LZW loss is pretty easy to implement - instead of exactly matching longest string from dictionary just pick long string that is acceptably similar.

I think there are 3 options:

* Make deflate backreferences match more, e.g. create lossy suffix tree to replace similar-but-not-exactly-same runs of pixels with identical ones. But how can you do it optimally, without copying pattern to areas of the image that deflate may choose to compress differently?

* Make deflate RLE match more. Replace runs of similar pixels with identical ones, or a pattern as deflate can repeat more than single byte (this way perhaps lines wouldn't be as noticeable). It also can be applied under a filter, so a run of zeros would blur or create gradients.

* Posterize intensities. That would help compressing noisy areas - less distinct values would help Huffman encoding.


Plus all of this could be done on interlaced PNG, so the distortion would be spread around mostly in non-linear fashion.

[Matt Mahoney]

You can also take advantage of the eye's poor sensitivity to fine color detail. If you transform RGB to YUV (as with jpeg), you can vary the pixel values quite a bit without a noticeable effect as long as the Y (brightness) stays the same at each pixel and the average color over areas several pixels wide is also the same.

I did some experiments years ago where I found that the colors contribute to the overall brightness in a ratio of about red=2, green=4, blue=1. For example, if you increase red by 10 and decrease either green by 5 or blue by 20, then the brightness would appear the same. The effect is somewhat non-linear with brightness and can vary with the color controls of the monitor, so you might have to experiment.

[porneL]

That's what I've got so far. Original 473KB:


"Lossy" PNG 167KB:

[Bloax]

Well like that it'd be more worthwhile to just palettize it to 256 colors (~170KB) at the moment. :p
But hopefully that's just for now. :I

[porneL]

I'm all for paletted PNG (I've spent years developing pngquant ), but sadly for some images 256 colors is not enough no matter how good quantization is.

[Intrinsic]

Your "Lossy" is already down to 756 colours, and yet Bloax's one is 256 and visually looks far better, so there has to be a decent solution. I've seen many over the years(all the ones you linked and another but that had weird artefacts so wasn't usable)
Conversion to a different colour space(LAB for example) and working some magic on just the AB channel as to preserve the detail in the L channel could lead to some nice results.

Examples below, as you can see a slight gaussian blur(0.40 Radius) on the L channel causes sightly less image clarity whereas just working on AB at 2.0 you don't notice anything at all really but knocks a nice chunk off the file size(Just saved out using lvl9 through IrfanView). And from there you can work more magic i'd guess.

[porneL]

Yes, I'm aware of color sensitivity issues, but I don't see how to apply that to PNG compression, since PNG is RGBA-based.

Lenna image is pretty noisy, so in this case blur helps by reducing noise:


but also made hard edge harder to compress (e.g. imagine simple case of a single red pixel on white background - it's either one pixel to compress, or 9 different pixels if you blur color channel).

I've tried to remove noise in way that I thought would be ideal for DEFLATE - by creating runs of identical pixels (like lossy RLE compression), but unfortunately that didn't improve much.

[porneL]

Ideally I should be modifying image only based on feedback from DEFLATE compressor, rather than degrading whole image up front.

Can you suggest an easy-to-hack DEFLATE implementation? zlib is optimized for speed, so it's not easy to change. I've tried to make it "match" bytes in a lossy way, but that created artifacts I did not expect (I presume I screwed up some of it's clever optimisations).

[porneL]

Sweet, open-source implementation of lossy X/Y filter: https://github.com/foobaz/lossypng (and now implemented in ImageAlpha)