I have a tileset generator. It grabs all unique tiles from an image and makes a new PNG out of them. You know how tilesets work.

I tried homebrewing a compressor/decompressor algorithm that mimicked the NES's 2-bits-per-pixel method. Lots of bit-packing. Every two bits indexes a color in that sprite's palette.

I saw some success with my algorithm when a 16-by-16px sprite was 1) only two colors and 2) symmetrical both horizontally and vertically. It turned such a 227-byte PNG into 8 bytes! It could then decompress it in a millisecond, which seems slow for such a small image. But I'll accept it.

But when I used 7 colors and needed 4 bpp, the compressed image would be larger than the original. 

So then I tried just using PyPNG. It takes the same 227-byte, two-color  image I mentioned before and compresses it to 81 bytes. That seems wrong.

But the same PyPNG method does turn my attached, 7-color michael.png (548 bytes) into michael_output.png (327 bytes). Code snippet's below:    

w = final_tileset.shape[1]
h = final_tileset.shape[0]
writer = png.Writer(w, h, bitdepth=bitdepth, palette=color_palette) #bitdepth is 4 in this case, and palette has 7 RGB vals.
output_file = open("michael_output.png", "wb")
writer.write(output_file, final_tileset_iterable)

Seems like I could still squeeze it even smaller somehow. I'm sure you seasoned pros have a few tricks up your sleeves for this. How small can I possibly make this particular attached image?

Quantitatively, I don't see how decompressing a 8 byte file could be practically better than decompressing a 81 byte or 227 byte file for performance purposes: for any users of the images your tool produces, decompression will take negligible time and memory on tiny sprites.

The most important thing you can do for the performance of games using your sprites is probably consolidating frames and tiles into relatively large images to reduce per-file overhead, without bothering with fancy compression techniques that become valuable only in extreme and unlikely situations.

6 hours ago, LorenzoGatti said:

The most important thing you can do for the performance of games using your sprites is probably consolidating frames and tiles into relatively large images to reduce per-file overhead, without bothering with fancy compression techniques that become valuable only in extreme and unlikely situations.

 

Thanks Lorenzo. I've been considering that this morning. Every PNG has a header too, so putting everything in the same PNG would save memory too.

6 hours ago, LorenzoGatti said:

Quantitatively, I don't see how decompressing a 8 byte file could be practically better than decompressing a 81 byte or 227 byte file for performance purposes: for any users of the images your tool produces, decompression will take negligible time and memory on tiny sprites.

That's fine. But practicality aside, let's humor the question for the fun of making the smallest game data possible. When I see games like Pokemon Red/Blue and Zelda 1 capture imaginations everywhere, it makes me want to similarly charm people using the fewest bytes possible. Just for the joy of it.

The walking frames seems very similar you might be able to store the diff between them instead of the full frame.

EDIT: You couldn't rely on a simple RGB color diff to get results. Instead, the "color" of the diff image would just be an integer representing the offset of the color index from the pallete. So if the color is the same between two images it would be 0. Moving from the first color to the second color in the pallete would be a 1, moving from the second color back to the first would be (colorCount - 1), so 3 if you had only 4 colors in your image.

The goal of the diff is to reduce entropy in the image and create as many continuous pixels that are the same as possible. This diff technique would only give you savings for frames that stay mostly the same. It may be difficult for a computer find similar images so there may be a manual process telling the computer what frames of animation go together.

1 hour ago, HappyCoder said:

Instead, the "color" of the diff image would just be an integer representing the offset of the color index from the pallete.

Thanks. So I take it the frame that's similar enough to be considered a "diff" frame would have this data something like this (assuming my image and animation data stored separately in disk):

1. Source frame index (or source tile, depending which saves more room for this info)
2. Destination frame index where this image will go
3. Top left corner of the rectangular area where the difference is
4. Bottom right corner "..."
5. Signed integer for the color index difference

Am I on the right track? Google is suprisingly unhelpful for a "sprite image diff" search. Similar keywords didn't help either.

I just came up with a name for that. I don't really know if there are any existing resources about it. I was just looking at your sprite for any places there is a lot of redundancy and brainstorming ways to reduce that redundancy.

I think you are on the right track. If you look at the image I attached you can get a feel for what I was trying to get at. The first frame of an animation is stored normally. Every next frame is stored as the difference from the previous frame. Since you are using a color pallete instead of RGB values you would store the number you need to add to the previous frame index value to get the new value. So as a simple example suppose you had the  image

0 1 1 0

1 2 2 1

1 3 3 1

0 1 1 0

and another (notice only the second row of pixels change)

0 1 1 0

0 2 3 0

1 3 3 1

0 1 1 0

the diff would be

0 0 0 0

3 0 1 3

0 0 0 0

0 0 0 0

Thanks for all your help.

44 minutes ago, HappyCoder said:

If you look at the image I attached you can get a feel for what I was trying to get at.

I see. Instead of storing that information in image data, I think I'll represent it as groups of rectangles per image. That way each group of changes is a couple bytes instead of a whole image. If a certain threshold of pixels between two frames is different though, I'll go ahead and declare the second frame a unique frame and store it in memory.

On 6/3/2019 at 1:41 PM, HappyCoder said:

I just came up with a name for that. I don't really know if there are any existing resources about it. I was just looking at your sprite for any places there is a lot of redundancy and brainstorming ways to reduce that redundancy.

I think you are on the right track. If you look at the image I attached you can get a feel for what I was trying to get at. The first frame of an animation is stored normally. Every next frame is stored as the difference from the previous frame. Since you are using a color pallete instead of RGB values you would store the number you need to add to the previous frame index value to get the new value. So as a simple example suppose you had the  image

0 1 1 0

1 2 2 1

1 3 3 1

0 1 1 0

and another (notice only the second row of pixels change)

0 1 1 0

0 2 3 0

1 3 3 1

0 1 1 0

the diff would be

0 0 0 0

3 0 1 3

0 0 0 0

0 0 0 0

I know you're onto something HappyCoder, but the problem in that solution is that I'm storing my images as greyscale images where the pixel values are indices to color palettes. That means storing a difference in index values like the one above means I'm just storing something as big as the original image anyway.

I'm gonna tinker with RLE'ing the difference images. And if the RLE'd diff image is significantly smaller than the original, I'll store it and cut the orig.