Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Optimal image compression for this specific style of image  (Read 1821 times)
0 Members and 1 Guest are viewing this topic.
Offline Crucio

Senior Newbie





« Posted 2009-04-21 16:17:07 »

Hi, I was wondering if I can use some of your knowledge to decide what the best (time vs. performance) compression algorithm is for a given type of image.

I'm dealing with a 2D array of ARGB values (therefore 4 bytes per pixel). The image is a screenshot of a flash game which is using vector graphics, and has very few colours, with the colours repeating often.

Here's an example image take from a google search.


Using an inbuilt zlib algorithm I achieved high compression but it took a long time. I'm aware that I could probably compress nearly as well if I take advantage of the image having few colours which are repeated often.

My first attempt was using simple run-length encoding with the sections being 4 bytes (to account for ARGB), this was very quick but didn't compress amazingly well.

Does anyone have any ideas on what algorithms or techniques would work well with this type of image?
Offline DzzD
« Reply #1 - Posted 2009-04-21 16:30:14 »

you will probably get very good results with GIF using 16 colors.

if you cant deal with GIF you can derivate the image line by line (as in video image derivated from previous one) :
substracte each line from the previous one and then compress the result with RLE

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #2 - Posted 2009-04-21 16:58:17 »

Have you tried storing them as pngs and putting them through pngcrush? IIRC it will attempt to find the colour format and bit depth which produces the smallest possible size for a given image.

An interesting alternative would be to distribute the actual vector files and convert them into images at boot or level load. Slick's svg support should be complete enough to handle this task.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2009-04-21 17:02:50 »

I'd follow DzzD's strategy, but with a twist.

In the sample image (make sure you don't use JPG as an input image..!) there are regions with much more different colors than others, and due to anti-aliasing, every pixel in a sequence of N is very likely to be different. RLE is not ideal here.

My suggestion is to have a preprocessing step, analyzing NxN (8x8 or 16x16?) patches of pixels, and *removing* them from the image. You fill those square holes with the pixels in the line just above the hole.

Then you apply DzzD's pixels => line_diff => RLE, which will compress extremely well, due to the lack of the 'noisy patches'.

Then compress the 'noisy patches' with an algorithm more suitable than RLE (GZ or JPG?), and store the coordinates of the patches, so that you know where you should put them back.

I don't know how much this will save you, but it might save a fair chunk.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Crucio

Senior Newbie





« Reply #4 - Posted 2009-04-21 17:11:15 »

If I hand coded that, how costly in terms of processing time do you think it will be compared with using Java's Deflater class, which I believe uses zlib?
Offline Crucio

Senior Newbie





« Reply #5 - Posted 2009-04-21 17:17:45 »

Could one of you explain the line difference algorithm a bit more, or pass a link to it?

If RLE is useful for when you have repeating numbers in the horizontal direction, is the line difference used to help with repeating numbers in the vertical direction?
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2009-04-21 17:25:41 »

typically there is a coherence in pixels next to eachother, not only horizontal, but also vertical.

0 = red
1 = blue

INPUT
1. 0010101111000010110000011
2. 0010110111100010110001011
3. 0000110111100001110001111
4. 0000110111110001111001111




take the diff between line 1 and 2, and store it in line 2
1. 0010101111000010110000011
2. 0010110111100010110001011
-------------------------------------------
2. 0000011000100000000001000

take the diff between line 2 and 3, and store it in line 3
2. 0010110111100010110001011
3. 0000110111100001110001111
-------------------------------------------
3. 0010000000000011000000100

take the diff between line 3 and 4, and store it in line 4
3. 0000110111100001110001111
4. 0000110111110001111001111
-------------------------------------------
4. 0000000000010000001000000


INPUT
1. 0010101111000010110000011
2. 0010110111100010110001011
3. 0000110111100001110001111
4. 0000110111110001111001111

OUTPUT
1. 0010101111000010110000011
2. 0000011000100000000001000
3. 0010000000000011000000100
4. 0000000000010000001000000

You can see there are much more zero's now, which means RLE gets more efficient.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Crucio

Senior Newbie





« Reply #7 - Posted 2009-04-21 17:30:26 »

Thanks, that makes sense. I'm probably being an idiot but I can't work out how to get back to the original input if given the output?

Edit: Ignore.. just realised the first line of the output is unchanged  Tongue
Offline DzzD
« Reply #8 - Posted 2009-04-21 17:33:35 »

If you derivate line by line you will end with a nearly black image that will be easier/more efficient to compress.

once derivated :
1  
2  
3  
4  
5  
for(int y=1;y<height;y++)
for(int x=0;x<width;x++)
pixel[x+y*width]-=pixel[x+(y-1)*width];

PS: this is a pseudo code... not working


you can compute how many color each line have and make a simple RLE (or other) compression.

as mentionned by Riven, dividing in smaller chunk (16*16) can help a lot as several sub-image (16*16) will be only one color and can be compressed in one or two Bytes.


EDIT: sorry if this post is useless but I wrote it before seing answers was posted... and I dont want to throw it Smiley





Offline Crucio

Senior Newbie





« Reply #9 - Posted 2009-04-21 17:48:49 »

Thank you both, I'll have a play and see how it goes.

(And thanks Orangy Tang, but I probably have to deal with the raw data rather than an actual file such as png)
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Abuse

JGO Knight


Medals: 14


falling into the abyss of reality


« Reply #10 - Posted 2009-04-21 20:13:05 »

If I hand coded that, how costly in terms of processing time do you think it will be compared with using Java's Deflater class, which I believe uses zlib?

If you are making performance comparisons between algorithms, you should be aware that Java's in-built Deflater implementation should be considered broken from a performance perspective.

There was a performance regression (upto 10 times slower!) way back in 1.5.0_07, and has yet to be fixed.
The bug is here (submitted 16-MAR-2006 =/ )

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Crucio

Senior Newbie





« Reply #11 - Posted 2009-04-22 09:11:32 »

Interesting, thanks for letting me know.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (29 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (40 views)
2014-12-09 22:41:13

BurntPizza (75 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (50 views)
2014-12-03 16:27:13

CopyableCougar4 (47 views)
2014-11-29 21:32:03

toopeicgaming1999 (113 views)
2014-11-26 15:22:04

toopeicgaming1999 (100 views)
2014-11-26 15:20:36

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!