Author Topic: Image Compression Help  (Read 3131 times)

0 Members and 1 Guest are viewing this topic.

Offline FinaleTI

  • Believe in the pony that believes in you!
  • CoT Emeritus
  • LV10 31337 u53r (Next: 2000)
  • *
  • Posts: 1830
  • Rating: +121/-2
  • Believe in the pony that believes in you!
    • View Profile
    • dmuckerman.tumblr.com
Image Compression Help
« on: February 21, 2011, 12:35:39 pm »
For Pokemon TI, I've been thinking about the sprite data I'd need.
I'm looking at about 77312 bytes just for the battles sprites (this is the total for front and back, but it's still a lot).
I was wondering if someone could help me with compressing the images.

They're 4 lvl greyscale and here's a sample of the hex data:

Bulbasaur Hex Code:
Code: [Select]
PART_1:
00000080
00000100
00000240
00001C20
000320A0
00088120
00120100
00240110
0048C208
06492214
097E1214
0982140A
0018180A
08310C0A
14032612
12043102
1E0680E0
2C068244
20018648
4FFA4670
C0040980
43FC0010
21020208
10801408
0740E40C
00900804
00860804
0001F804
00105608
000611C8
00012090
0000C060

PART_2:
00000080
00000140
00000260
00003CA0
000721A0
000881A0
001203A0
00340F10
007EFF18
067F3F1C
097E3F1C
09827E1A
0019FC1A
0833FE3A
1407FFFA
120CFFF2
1E0EFFE6
2C06FFEC
2003FFF8
5FFE7FF0
C2041FE0
43FC1FF0
21023E78
1B817E18
07C0FC1C
00B0FC1C
008FF81C
0043FC1C
0033F7F8
000FF1F8
0001E0F0
0000C060

If someone could help with this, it would be greatly appreciated.


Spoiler For Projects:

My projects haven't been worked on in a while, so they're all on hiatus for the time being. I do hope to eventually return to them in some form or another...

Spoiler For Pokemon TI:
Axe port of Pokemon Red/Blue to the 83+/84+ family. On hold.

Spoiler For Nostalgia:
My big personal project, an original RPG about dimensional travel and a few heroes tasked with saving the world.
Coding-wise, on hold, but I am re-working the story.

Spoiler For Finale's Super Insane Tunnel Pack of Doom:
I will be combining Blur and Collision Course into a single gamepack. On hold.

Spoiler For Nostalgia Origins: Sky's Story:
Prequel to Nostalgia. On hold, especially while the story is re-worked.

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: Image Compression Help
« Reply #1 on: February 21, 2011, 01:50:23 pm »
i most certainly am not an expert on data compression, but i can see a fairly simple method that would shrink it a bit.

At present, each pixel is represented in the data by two bits (one to determine if the back buffer is set or reset, and one for the front buffer, yes?). Well, it looks like, in your image here, you have quite a bit of horizontal colour repetition, meaning a form of rle wouldn't be all that bad. The method I was thinking of would ascribe four bits to each pixel, the first two to determine colour and the next two to hold the number of pixels in a row of the same colour(1-4). This means that, although the data representing a single pixel is doubled, the data representing four contiguous pixels of the same colour is halved.
currently, your sprite takes up 256 bytes of data, but using this method it would be compressed to 241.5. Obviously, it's not a huge decrease(5.6%), and it may not work even this well for your larger sprites, but it's an idea.
Another possibility is, if large sections of white space are a common theme in your sprites, using this method only for white pixels and leaving other colours to the two bit method, or even using the method for every colour but black, which seems to show up mostly in a single pixel wide, form-defining barrier around the outside of your sprites and not in large areas. I don't feel like calculating these by hand right now, but I think compressing only white is the method most likely to work best on this bulbasaur.
« Last Edit: February 21, 2011, 01:50:55 pm by shmibs »

Offline FloppusMaximus

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 290
  • Rating: +57/-5
    • View Profile
Re: Image Compression Help
« Reply #2 on: February 21, 2011, 03:56:32 pm »
Those are good ideas.  I'd add that in this case, since there are only 3 possible values, you can save some space immediately by encoding the most common (white) as only one bit, while using two bits for the other two possible values.  In the more general 4-level case, you'll probably still see some benefit from Huffman coding (encode the most common value as one bit, the second most common as two bits, and the two least common as three bits.)

Also, consider using a more flexible RLE format, since there are many runs longer than 4 pixels.  For instance, 0xx to represent a run of 1 to 4 pixels, or 1xxx to represent a run of 5 to 12 pixels (not saying this is optimal - I haven't done the math - this is just to give you an idea.)

In the example, the white runs are generally longer than the gray runs; the black pixels are predominantly isolated, so probably not worth using RLE at all.

Looking at it from another angle (as it were), you might find it beneficial to encode the difference between one row and the next, rather than encoding each row separately.

Try a lot of methods and see what works.

Also:
Quote
...black, which seems to show up mostly in a single pixel wide, form-defining barrier around the outside of your sprites...
This raises an interesting point: if every sprite follows the rigid pattern that each non-empty row begins with n white pixels and one black pixel, and ends with one black pixel and m white pixels, you could take that into account, and encode the beginnings and ends of your rows specially.
« Last Edit: February 21, 2011, 04:02:32 pm by FloppusMaximus »

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: Image Compression Help
« Reply #3 on: February 21, 2011, 04:41:51 pm »
or maybe one could exclude the surrounding white pixels altogether?
Because there is a border of white pixels surrounding everything that is drawn, maybe one could begin the data for each line with a five bit string dictating where to start drawing pixels that aren't white(meaning that any intro stretch of more than two white pixels would yield saved space)?
This on it's own, even if you kept the two bit method for the remainder of each line past that, would shrink your bulbasaur to 208.25 bytes(an 18.6% decrease).