Optimal image compression for this specific style of image

Newbie & Debugging Questions
#1

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?

#2

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

#3

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.

#4

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.

#5

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?

#6

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?

#7

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
  1. 0000011000100000000001000

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

  1. 0010000000000011000000100

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

  1. 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.

#8

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 :stuck_out_tongue:

#9

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

once derivated :

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 (1616) can help a lot as several sub-image (1616) 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 :slight_smile:

#10

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)

#11

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 =/ )

#12

Interesting, thanks for letting me know.