Results 1 to 12 of 12

Thread: Lossy DEFLATE, lossy PNG

  1. #1
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post

    Lossy DEFLATE, lossy PNG

    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?

  2. #2
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    448
    Thanks
    1
    Thanked 101 Times in 61 Posts
    Quote Originally Posted by porneL View Post
    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.

  3. #3
    Member
    Join Date
    Jul 2013
    Location
    Germany
    Posts
    24
    Thanks
    4
    Thanked 4 Times in 4 Posts
    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.

  4. #4
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    @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.
    Last edited by porneL; 23rd July 2013 at 03:34.

  5. #5
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    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.

  6. #6
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    That's what I've got so far. Original 473KB:
    Click image for larger version. 

Name:	Lenna.png 
Views:	364 
Size:	462.2 KB 
ID:	2390 Click image for larger version. 

Name:	Lenna-thermal.png 
Views:	348 
Size:	52.6 KB 
ID:	2392

    "Lossy" PNG 167KB:
    Click image for larger version. 

Name:	Lenna-18levels.png 
Views:	385 
Size:	163.1 KB 
ID:	2391 Click image for larger version. 

Name:	Lenna-18levels-thermal.png 
Views:	326 
Size:	46.9 KB 
ID:	2393

  7. #7
    Member Bloax's Avatar
    Join Date
    Feb 2013
    Location
    Dreamland
    Posts
    52
    Thanks
    11
    Thanked 2 Times in 2 Posts
    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

  8. #8
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    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.

  9. #9
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    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.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	Leena_AB blurred at 2.0.png 
Views:	289 
Size:	397.0 KB 
ID:	2398   Click image for larger version. 

Name:	Leena_AB blurred at 2.0 - L at 0.40.png 
Views:	309 
Size:	381.8 KB 
ID:	2399  

  10. #10
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    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:

    Click image for larger version. 

Name:	Leena_AB blurred at 2.0 - L at 0.40-t.png 
Views:	323 
Size:	74.2 KB 
ID:	2400Click image for larger version. 

Name:	Leena_AB blurred at 2.0t.png 
Views:	353 
Size:	77.6 KB 
ID:	2401
    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.

  11. #11
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    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).

  12. #12
    Member
    Join Date
    Jul 2013
    Location
    UK
    Posts
    17
    Thanks
    5
    Thanked 1 Time in 1 Post
    Sweet, open-source implementation of lossy X/Y filter: https://github.com/foobaz/lossypng (and now implemented in ImageAlpha)
    Click image for larger version. 

Name:	Lenna-averagefilter-12.png 
Views:	304 
Size:	104.6 KB 
ID:	2423Click image for larger version. 

Name:	Lenna-averagefilter-12-thermal-fs8.png 
Views:	341 
Size:	29.8 KB 
ID:	2424
    Last edited by porneL; 19th August 2013 at 21:05.

Similar Threads

  1. WebP (lossy image compression)
    By Arkanosis in forum Data Compression
    Replies: 62
    Last Post: 12th April 2019, 19:45
  2. jpeg to zpaq lossy compression
    By toi007 in forum Data Compression
    Replies: 11
    Last Post: 24th January 2013, 04:20
  3. lossy simplifier of a png bmp jpg
    By toi007 in forum The Off-Topic Lounge
    Replies: 7
    Last Post: 7th July 2012, 01:44
  4. Lossless vs. Lossy
    By WillatSMU in forum Data Compression
    Replies: 7
    Last Post: 11th May 2012, 18:29
  5. Lossy 3D Object transformation
    By EwenG in forum Data Compression
    Replies: 13
    Last Post: 24th February 2011, 14:29

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •