#32850 - ScottLininger - Tue Dec 28, 2004 6:08 pm
I've seen a number of tools that take a bitmap image and convert it to tiles and a map, but I can't find one that can take a bitmap image and REDUCE the total number of tiles to a given maximum. (Essentially a tile quantizer, if you get my meaning.)
I've started research on how to write one of my own, but it's a hairy enough algorithm that I thought I'd ask if anyone knows of one I could just use.
If one doesn't exist, I'd love to hear people's votes for their favorite BMP2TILE tool, so I could look at its features and build my tool to have a similar interface. (Why reinvent the wheel?)
Thanks!
-Scott
#32858 - tepples - Tue Dec 28, 2004 8:32 pm
It's not exactly what you want, but if you were considering using 256-color tiles and were thinking of reducing VRAM usage by reusing tiles, then consider using Quither, which quantizes an image into 16 palettes of 15 colors, saving half the VRAM that way. If you want it, Search the board for Quither.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#32867 - ScottLininger - Tue Dec 28, 2004 9:46 pm
Yeah, Quither is awesome (thanks, Dekutree). I actually started with the quither source code and am working to expand it to quantize tiles in addition to palettes.
My ultimate goal is to build (for learning purposes) an open-source, tile-driven video "codec" for the GBA. It seems to me that one could get pretty decent compression by building a tile quantizer that works across all of the frames of a movie. As for the *quality* of the video, that's really hard to visualize until it's working. It'll probably stink. ;)
But... getting a tool that can optimize the number of tiles is the first step. I have code that is successfully pulling frame data out of an AVI file, so now I need to do something with it.
-Scott
#32876 - tepples - Tue Dec 28, 2004 10:43 pm
That's called vector quantization.
However, any video codec without some form of motion compensation won't give much of a compression ratio. Look for peaks in the covariance of two frames at various spatial lags, and then offset the whole image by that amount when copying it to the next frame.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#32999 - DekuTree64 - Thu Dec 30, 2004 12:32 am
I don't think there are any freeware tile reducers, although there is a professional tool that can do it, so it's certainly possible.
I've been doing some pondering on the tile reducing problem since yesterday, but haven't come up with a sure-fire solution yet. The best I've come up with is a fairly slow sort of brute-force comparison of all the tiles against eachother, making lists of all the ones that can be merged based on a given maximum error level.
What I'm trying to think of now is a way to combine it with the Quither algorithm, which is to split the tiles into 16 groups and then quantize each group seperately. That would be easy enough to split them up, reduce tiles, and then quantize, but it'd look horrible using the same 16x16 palette on a whole movie.
So, I'm looking for a way to make groups that can last for as many frames as they are useful (allowing the tile reduction to be done on all tiles from that group over several frames), but can be removed later on to make room for a new group with a new palette.
What I'm thinking is to split each frame up into 8x8 tiles, average the colors of each tile, and quantize them into 16 groups (ala Quither), and then compare them to the 'group colors' of neighbor frames to find groups that are similar enough to quantize together.
I don't know if you could really get a good compression ratio with such a codec, but it's certainly an interesting idea. I've thought about attempting it before actually, but then decided not to since I didn't have a real use for it.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#33072 - ScottLininger - Thu Dec 30, 2004 5:41 pm
| DekuTree64 wrote: |
| I've been doing some pondering on the tile reducing problem since yesterday, but haven't come up with a sure-fire solution yet. The best I've come up with is a fairly slow sort of brute-force comparison of all the tiles against eachother, making lists of all the ones that can be merged based on a given maximum error level. |
There would probably need to be some sort of tile averaging piece to that. If two tiles are within X percent of one another, you might get better results by blending them.
| Quote: |
| but it'd look horrible using the same 16x16 palette on a whole movie. |
Like you said, eventually one could have some trigger that recognizes when a new scene (with substantially different colors) has appeared, and it would recalculate the palette for insertion at that point.
Another possibility for the first version would be to reduce an entire movie to 16-color, dithered grayscale. This would simplify the problem down to a single 16-color palette, and it would make tile averaging a snap. Once that part was working, one could start figuring out how to expand the algorithm to a larger set of palettes.
| Quote: |
| I don't know if you could really get a good compression ratio with such a codec, but it's certainly an interesting idea. I've thought about attempting it before actually, but then decided not to since I didn't have a real use for it. |
Yeah, it's very hard to tell without trying it. It might not be the best compression, but the advantages to using tile mode instead of mode 3 or 4 are potentially immense. There's a small enough amount of data changing each frame that I think you could get a reasonable framerate even with several layers of video playing at once.
A really mature codec of this kind could recognize things like camera pans and implement them by scrolling your layer rather than swapping out tiles.
But I think the first question is whether it would even look good enough to be worth trying... It might be so pixelated and jumpy that it's not worth going any further. I'll goof with it in my copious free time. ;)
-Scott
#33074 - ScottLininger - Thu Dec 30, 2004 5:55 pm
Dekutree,
I'm not sure if you're interested, but the avi frame-grabbing code I have is running in VB.
http://www.shrinkwrapvb.com/avihelp/avihelp.htm
Here's an example of messing with AVIs in c++, though I haven't been able to get this working yet.
http://www.adp-gmbh.ch/win/programming/avi/
The examples on that page are more about creating AVIs than in decomposing them... but it would probably get you started.
There's also a shareware tool called KONVERTOR that I found some time ago that will convert an AVI out into BMPs. This might be an easier route to go for initial testing. Here's the guy's site. He has trial versions available for free, and registration is cheap.
http://www.logipole.com/indexe.html
Or you download it from my site:
http://www.thingker.com/Konvertor.zip
Cheers,
Scott
#33121 - DekuTree64 - Thu Dec 30, 2004 11:17 pm
| ScottLininger wrote: |
| There would probably need to be some sort of tile averaging piece to that. If two tiles are within X percent of one another, you might get better results by blending them. |
Yeah, that's what I had in mind. Make lists of tiles that are similar, and then average the pixels of all the tiles in each list. The tricky part is making sure a tile doesn't get included in more than one list (my first algorithm would have totally blown up due to that). I'll write up a full description of the algorithm later after I take care of some things.
| Quote: |
| Another possibility for the first version would be to reduce an entire movie to 16-color, dithered grayscale. |
Yeah, that is a possibility. It probably would be a lot easier to get it running, and still be pretty easily expandable to handle palette swapping.
One problem though is that Quither-style dithering is done as a final step after the palette quantizing, but the tile reduction has to be done BEFORE palette quantizing (since the averaging needs to use direct color). Then the dithering would mess up all the unified tiles.
I suppose you could quantize/dither first, and then reduce tiles and re-re-map the averaged colors without dithering. Might make the combined tiles stand out too much though.
| Quote: |
Yeah, it's very hard to tell without trying it. It might not be the best compression, but the advantages to using tile mode instead of mode 3 or 4 are potentially immense. There's a small enough amount of data changing each frame that I think you could get a reasonable framerate even with several layers of video playing at once.
A really mature codec of this kind could recognize things like camera pans and implement them by scrolling your layer rather than swapping out tiles. |
I think it's worth trying, especially for having the advantage of 4-bit tiles.
Scrolling would also be cool, hadn't thought of that before. Not sure how to detect a scroll, but I'd be willing to bet that other codecs have done it.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#33128 - tepples - Fri Dec 31, 2004 12:48 am
| DekuTree64 wrote: |
| Scrolling would also be cool, hadn't thought of that before. Not sure how to detect a scroll, but I'd be willing to bet that other codecs have done it. |
That's where the covariance comes in. Look up "covariance" and "autocovariance" on Google. Essentially, you're multiplying two images' luma channels together pixelwise at various offsets and adding the products, and then you're searching for a peak level.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#33168 - DekuTree64 - Fri Dec 31, 2004 8:30 am
Ok, here's my idea on tile reduction:
Basic algorithm: Iterate over all possible pairs of tiles and make lists of similar tiles. Each list is then merged into a single tile, by averaging the pixel colors of all the tiles in that list.
The error between two tiles is computed by taking sum i = 0 to 8*8 of (tile1[i].r - tile2[i].r)^2 + (tile1[i].g-tile2[i].g)^2 + (tile1[i].b-tile2[i].b)^2. Try again for each of the possible H/V flippings of the tiles and keep the smallest one. Tiles are considered 'similar' if the error is below a user-specified threshold.
Building the lists: Create an array of circluar, doubly linked list 'heads', one for each tile. Each list entry has 2 members, a 'next' and 'previous' tile index, both initialized to invalid.
Loop i over all tiles, and loop j from i+1 to tileCount (so as not to check duplicates). If tile j is similar to tile i, then traverse j's current list and find the largest error between j and any other tile in its list. Also find the largest error between j and any tile in i's list. If the largest error in i's list is less than that in j's current list, unlink j and add it into i's list.
(Think of i as the 'hunter' tile, trying to gather as many j tiles into its own list as it can)
Once the lists are all built, they need to be separated out. Say tiles 0, 1 and 2 are in a list. If you traverse 0's list, you get "0, 1, 2", and then wrap back around to 0 so you know you hit the end of the list. If you traverse 1's list, you get "1, 2, 0", and 2's is "2, 0, 1". All the same circular list, just that they each think they're the head.
Separating the lists: Make an array of 'valid flags', one for each list, and initialize them all to TRUE. Also make a new array of list heads, and a 'list count', initialized to 0. Loop over the lists. If a list's valid flag is still TRUE, traverse it, setting each tile's valid flag to FALSE, preventing them from forming their own duplicate lists. Also add the list into the new list array and increment the list count.
When that's finished, each entry in the new list array is ready to be merged into a tile (and so the 'list count' is your new number of tiles).
Well, that took a while longer than I was hoping it would to explain properly, and it went through a few revisions in the process. It's also O(n^3), so it might be too slow for practical use.
Could be sped up by using n^2 memory, storing the error between each pair of tiles as you go to make finding the 'largest error' for a tile in a list just a straight search and compare, but that wouldn't reduce the actual complexity.
Hopefully it will give you some ideas though. Let me know if anything didn't make sense (or if anything did? :) ).
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#33196 - ScottLininger - Fri Dec 31, 2004 5:59 pm
Deku,
That seems like a reasonable starting algorithm. Here are a couple of random thoughts I had after reading your post. These are probably not big considerations at this point, since they have to do with the potential for a video codec and NOT just with tile quantizing, but I thought I'd write 'em down while I was thinking about them.
For speed improvement, you could limit the number of frames that you process to get your tileset (maybe every 12th frame or something) and then do a post-processing step to actually output the entire video. Here the logic would be simply "which tile am I closest to?" for each 8x8px piece.
Granted, this gets really weird once you've turned everything out into 16x16 palettes... There might be value in sorting each palette from lightest to darkest, so that a quick & dirty "difference" comparison could be done just by looking at indexes. Might allow you to very quickly determine which tiles are *probably* the closest, and then you could do a more detailed step that figures out which tile and palette is really the best.
The question is, would you really save anything if the post-processing step becomes almost as hairy as the initial tile determination phase? Processing an ideal set of tiles from even a 5-minute, 12fps movie is a LOT of work, but I'm used to worrying about performance on a GBA, not a PC... Maybe it's not so bad.
Again, limiting the palette to black & white or to some other pre-structured palette (one could use the "web" palette, for example) might be worth thinking about.
The most basic "compression" that should be supported is the ability to tell when a block of tiles has remained the same from frame to frame. Strips of unchanged tiles could then be compressed into a single data element that describes how many unchanged tiles are to follow... Slows down the display-side code but that's probably worth it to save ROM space.
-Scott
#33226 - DekuTree64 - Fri Dec 31, 2004 10:57 pm
Hmm, I don't know about that postprocessing step. It doesn't seem like it would reduce the actual tile count any further. Might bump up the quality a bit though, allowing a higher allowed error level on the tile quantizing, which would in turn save on tiles.
One handy thing is that the octree quantizer that Quither uses naturally sorts colors according to brightness, so no need to do anything special there.
Here's another idea I had. For deciding which parts of the screen are changing, I was thinking we could have several screen map types, and pick the best for each frame.
Type 0: A straight full 30x20 tile index map, probably only used on a whole screen change.
Type 1: A 30x20 bitmask, specifying which tiles changed, followed by a new tile index for each one that changed. Good for a few scattered tiles, and maybe optionally RLE the bitmask, if it has a lot of unchanged tile runs in it.
Type 2: A 1x20 bitmask, each bit specifying that a whole row should be replaced.
Type 3: 30x1 bitmask. One bit per column.
Type 4: Type 2 plus a 30x1 bitmask for each changed row.
Type 5: Type 3 plus a 1x20 bitmask for each changed column.
Type 6: Quadtree-type. Start by breaking the screen up into 4 128x128 blocks (even though only the top left block will fully fit on the screen).
Store 4 bits, specifying wether each of the 4 blocks has a changed tile in it.
If a block's bit is set, divide it into 4 more, and read 4 more bits, until you get to the lowest level. Copy the new tile indices for the block to the screen, then step back up a level and check the next block in the group, and so on.
The lowest level could be defined as exact tiles, or maybe 2x2 blocks of tiles.
The actual new tile index stream for the map could be compressed, and decompressed to a temporary location. Then use the bitmask to find out where each of those tiles goes on the screen.
On an unrelated note, another cool thing to add later on would be palette fading support, to reuse the same tile group, just with a different palette. Maybe check for 'proportional' colors between frames in the tile grouping phase.
Say you find a group of average bright red tiles on frame 1, and average dark red on frame 2, then scale the dark ones' pixel colors up to match the brightness of frame 1's, and run tile quantizing on them together.
Then run the palette quantizing, and for frame 2, scale the new palette down To match the dark ones' original level.
Maybe test to make sure all the individual pixels of the dark tiles are actually dark enough though. Otherwise you might try to scale up a mostly black tile that had a few bright red pixels. Then they'd get clipped back down and couldn't be restored properly by darkening the palette.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#35922 - J-Rod - Sat Feb 12, 2005 10:53 pm
Doesn't look like it was linked here on a quick scan of this thread, figure I'll plug Jsensebe's program here, Tile-Quant-Do.
http://members.cox.net/jsensebe/gba/
_________________
#gameart on EFnet. The pixel owns you.