Results 1 to 22 of 22

Thread: Compression of repetitive images (e.g. spritesheets)

  1. #1
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts

    Compression of repetitive images (e.g. spritesheets)

    When compressing images and especially game data, I often made the observation that some images compress worse using image compression algorithms (PNG and FLIF). Further analysing revealed that one of the cases when that happens is when the images are repetitive. Attached are two images, a real world example (source) and a generated image (random noise pattern 64*64, total size 512*512). Both PNG and FLIF perform bad here while general compression algorithms like LZMA or mixed ones (PAQ) can handle the situation.

    Code:
    786.486      gen.bmp (generated, 64*64 pattern)
    300.366      gen.flif (-e)
    253.216      gen.flif (-e -N)
    230.139      gen.flif (-e -N -R5)
    105.683      gen.png
     13.647      gen.pcf (Precomp 0.4.7, uses LZMA)
     12.775      gen.paq8p (-3)
     12.288      theoretical optimum (64*64*3)
    
    786.486      gen2.bmp (generated, 64*21 pattern)
    142.530      gen2.flif (-e)
     50.982      gen2.flif (-e -N)
      8.791      gen2.png
      5.400      gen2.pcf
      4.428      gen2.paq8p (-3)
      4.032      theoretical optimum (64*12*3)
    
    226.338      glitch.flif (-e)
    203.995      glitch.flif (-e -N)
    182.418      glitch.png
    133.693      glitch.pcf
    With the second test file (64*21 pattern) we can see that the 32K deflate window size limits PNG here, because in the 64*64 case, it takes 64 lines for a repetition and 512*64*3 = 98304 is out of the window, while in the 64*21 case, the pattern can be matched.

    So I just wanted to share these observations. Does somebody know a (lossless) image format that doesn't have this problem? Didn't try all the others (BPG, Gralic etc.) yet.
    Since I would prefer to use FLIF by default for image data in Precomp, this is a problem I'd like to solve, so a preprocessor that detects and replaces repetitive patterns in images would be the next step, I'll post further progress with this.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	gen.png 
Views:	31 
Size:	103.2 KB 
ID:	6621   Click image for larger version. 

Name:	glitch.png 
Views:	31 
Size:	178.1 KB 
ID:	6622  
    http://schnaader.info
    Damn kids. They're all alike.

  2. The Following User Says Thank You to schnaader For This Useful Post:

    Shelwien (22nd May 2019)

  3. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,075
    Thanks
    170
    Thanked 893 Times in 448 Posts
    Only video codecs have block matching unfortunately.
    It may be possible to port a I-frame compressor from AV1 or something.
    I guess you can also test "official" new codecs, like JPEG2000+, webp. Also maybe pik.

    I also had an idea for fast detection of 2D block matches - its possible to implement 2D anchor hashing (aka content-dependent chunking).
    Like, we can split horizontal and vertical lines of the image to 1D fragments, the use intersection points as block grid.
    Then it should be enough to look up / insert one hash per block.

  4. The Following User Says Thank You to Shelwien For This Useful Post:

    schnaader (23rd May 2019)

  5. #3
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Jpeg xl has some block matching. Block matching is not much better than line matching in practice. Also, these sprite images are not that much of the whole data volume that humanity has.

  6. #4
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    How did WebP lossless do?

  7. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,075
    Thanks
    170
    Thanked 893 Times in 448 Posts
    > these sprite images are not that much of the whole data volume that humanity has.

    They are pretty frequent in games.
    Then, there're also mipmaps.

  8. #6
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    WebP lossless does very well, this is what I wanted:

    Code:
    105.683      gen.png (generated, 64*64 pattern)
     12.980      gen.webp_lossless_m_1_q100
     12.750      gen.webp_lossless_m_6_q100
     12.288      theoretical optimum (64*64*3)
    
    210.768      glitch.webp_lossless_m_5_q_100 (time: 2 s)
    182.418      glitch.png
    133.693      glitch.pcf (time: 2 s)
    119.674      glitch.webp_lossless_m_6_q_100 (time: 7 s)
    The minor downside that it needs method 6 (slowest) for the big spritesheet, but this is the expected time/size balance. Decoding is fast (~10 ms).
    Last edited by schnaader; 27th May 2019 at 11:50. Reason: 100 ms (included PNG encoding) -> 10 ms
    http://schnaader.info
    Damn kids. They're all alike.

  9. The Following User Says Thank You to schnaader For This Useful Post:

    Shelwien (27th May 2019)

  10. #7
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    However, comparing WebP to FLIF on "normal" images, compression ratio is often worse, so I'll keep following the pre-processing trail for FLIF and look at the other intra-frame alternatives. Hints on how to get better ratios with WebP lossless are welcome.
    http://schnaader.info
    Damn kids. They're all alike.

  11. #8
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    WebP lossless does very well, this is what I wanted
    Try also cwebp -near_lossless 40 or -near_lossless 60

  12. #9
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    Decoding is fast (~100 ms).
    Something is wrong in either the build or the benchmarking, you should be able to get a decoding speed of around 2 ms.

  13. #10
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    Quote Originally Posted by Jyrki Alakuijala View Post
    Try also cwebp -near_lossless 40 or -near_lossless 60
    That's not my use case since I want the result to be lossless, but for the sake of completeness:

    Code:
    119.674      glitch.webp_lossless_m_6_q_100
    112.638      glitch.webp_near_lossless_80_m_6_q_100 (not lossless)
    103.340      glitch.webp_near_lossless_60_m_6_q_100 (not lossless)
     91.424      glitch.webp_near_lossless_40_m_6_q_100 (not lossless)
    Quote Originally Posted by Jyrki Alakuijala View Post
    you should be able to get a decoding speed of around 2 ms.
    Yes, this was the time for the whole call (including PNG encoding), -v outputs "Time to decode picture: 0.010s" (so ~10 ms).

    By the way, is "-mt" limited to 2 threads? I get a 2x speedup even with 4 cores (and HT).
    http://schnaader.info
    Damn kids. They're all alike.

  14. #11
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    Yes, this was the time for the whole call (including PNG encoding), -v outputs "Time to decode picture: 0.010s" (so ~10 ms).
    perhaps timer resolution in your system is 10 ms, and system gives a minimum of one quant

    Quote Originally Posted by schnaader View Post
    By the way, is "-mt" limited to 2 threads? I get a 2x speedup even with 4 cores (and HT).
    I am not aware of a multithreaded decoder (or encoder) for webp lossless. I don't know what if anything the -mt does.

    Does any aspect of WebP lossless run faster with -mt flag?

  15. #12
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    That's not my use case since I want the result to be lossless, but for the sake of completeness:
    If the game is for humans, you should likely be using quality 60. IIRC, quality 60 is still way better than webp lossy quality 100 or jpeg quality 97 or so.

    What is your use case?

  16. #13
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    Quote Originally Posted by Jyrki Alakuijala View Post
    What is your use case?
    Integrating into Precomp - so e.g. the images can come from a container, a ZIP, a PDF or a transcoded PNG and have to be reconstructed bit-to-bit identical or the routines that use them will fail (checksum failure etc.).
    http://schnaader.info
    Damn kids. They're all alike.

  17. #14
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    Integrating into Precomp - so e.g. the images can come from a container, a ZIP, a PDF or a transcoded PNG and have to be reconstructed bit-to-bit identical or the routines that use them will fail (checksum failure etc.).
    Consider adding a near lossless mode into precomp then.

  18. #15
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    Quote Originally Posted by Jyrki Alakuijala View Post
    Consider adding a near lossless mode into precomp then.
    Already thought about that, but it would involve too much work. I'd have to support many image/video/audio formats and also containers like ZIP and patch at least the most obvious meta data (checksums, file length etc.). Also, there are less use cases and it'd always involve a trial/error stage to test if your files still work as expected. FileOptimizer is such a lossy recompressor, so solutions already exist.
    http://schnaader.info
    Damn kids. They're all alike.

  19. #16
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,075
    Thanks
    170
    Thanked 893 Times in 448 Posts
    There's no use case for lossy recompression.
    It can't be implemented universally - only for specific container formats, otherwise the programs using these containers won't work.
    And game repackers do try lossy approach occasionally - users don't like that and would look for a lossless repack.
    Its best to just leave encoding quality to content creators.

    As example, would you like it if git didn't preserve source formatting, because it saves 10% of compressed size?

  20. #17
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    By the way, looking at the bitstream spec for WebP, it says that the LZ77 stage has a max distance of 1.048.576 pixels. For 24-bit images, this would lead to a maximum distance of 3.145.728 bytes which could be confirmed in my tests:

    Code:
    image size	pattern size	match distance 				theoretical size	webP size
                                    (Image width * pattern width * 3)	
    
    4096		256		3.145.728				196.608			  216.946
    4096		257		3.158.016				198.147			3.166.432
    Last edited by schnaader; 27th May 2019 at 18:25. Reason: improving layout
    http://schnaader.info
    Damn kids. They're all alike.

  21. #18
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by schnaader View Post
    By the way, looking at the bitstream spec for WebP, it says that the LZ77 stage has a max distance of 1.048.576 pixels. For 24-bit images, this would lead to a maximum distance of 3.145.728 bytes which could be confirmed in my tests:
    The LZ77ish compression deals with internal pixels, which are RGBA, i.e., 4 bytes: both lengths and distances are in pixels, not in bytes. Occasionally more image pixels are packed into the green component of a single internal pixel (for example for a two color black/white image eight image pixels might be packed into a single pixel).

    WebP palette size is limited to 256 colors (nowadays I wish I had used 2048 or so as a limit), so there can be other non-linearities when the palette size exceeds 256.

  22. #19
    Member
    Join Date
    Jan 2017
    Location
    Germany
    Posts
    46
    Thanks
    24
    Thanked 9 Times in 6 Posts
    Quote Originally Posted by schnaader View Post
    Hints on how to get better ratios with WebP lossless are welcome.
    What about forking and tweaking the lossless compression algorithm of WebP? For the use in Precomp it hasn't to be compatible to the WebP specification.

  23. #20
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    658
    Thanks
    184
    Thanked 240 Times in 145 Posts
    Quote Originally Posted by WinnieW View Post
    What about forking and tweaking the lossless compression algorithm of WebP? For the use in Precomp it hasn't to be compatible to the WebP specification.
    How to improve on WebP lossless when cpu/format compatibility is not an issue:
    - add a few predictors with a larger support (1 %), current predictors are form a 3x3 neighbourhood (i.e., 4 pixels) due to decoding speed. A 5x5 support gives nice improvements for photographic images.
    - make the predictors customizable instead of fixed (1 %)
    - add context modeling (3 %)
    - add arithmetic coding (0.7 %)
    - larger window size (if you have larger repetitive images)
    - larger palettes (~1 %)
    - offset R and B by a custom amount in subtract green (1 %), this makes predictors work more efficiently

  24. The Following 2 Users Say Thank You to Jyrki Alakuijala For This Useful Post:

    schnaader (28th May 2019),WinnieW (28th May 2019)

  25. #21
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,075
    Thanks
    170
    Thanked 893 Times in 448 Posts
    Btw, what's the paq8px result for your images? As entropy estimation?

  26. #22
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    529
    Thanks
    191
    Thanked 168 Times in 76 Posts
    Quote Originally Posted by Shelwien View Post
    Btw, what's the paq8px result for your images? As entropy estimation?
    Basically, yes. Had the result and wanted to list it since it's so close to the theoretical optimum.
    http://schnaader.info
    Damn kids. They're all alike.

Similar Threads

  1. Replies: 0
    Last Post: 14th March 2015, 13:21
  2. Compression benchmarking: 64 bit images and 24 bit codecs
    By m^2 in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 30th November 2011, 17:01
  3. ISO images compression
    By Surfer in forum Data Compression
    Replies: 17
    Last Post: 24th March 2011, 22:16
  4. Idea for raising compression efficiency on disk images
    By Mexxi in forum Data Compression
    Replies: 10
    Last Post: 18th February 2010, 05:56
  5. Compression used in .wim (Vista) images
    By jaclaz in forum Data Compression
    Replies: 9
    Last Post: 29th August 2008, 18:05

Posting Permissions

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