Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - RgbQuant-SMS - reduce the tile count of your images

Reply to topic
Author Message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
RgbQuant-SMS - reduce the tile count of your images
Post Posted: Sat Jan 17, 2015 10:44 am
Hello,

This is an experiment I'm making for converting an image to a SMS-compatible palette+tileset+map while keeping the number of tiles down to a predefined limit; it uses RgbQuant.js to reduce the number of colors, then it does the usual steps of dividing the image into tiles and removing the duplicates; finally, it uses clusterfck's k-means implementation to group tiles by similarity, and uses that information for merging together tiles that are similar enough.

RgbQuant-SMS demo

GitHub repository
  View user's profile Send private message Visit poster's website
  • Joined: 01 Jan 2014
  • Posts: 316
Reply with quote
Post Posted: Sat Jan 17, 2015 11:47 am
Nice.

Strange that the snes sms3 image a gradient is created to deal with the backdrop color change yet on the actual gradient images it sticks to solid colors. Is this about the configurations?
  View user's profile Send private message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sat Jan 17, 2015 12:13 pm
That seems to be because the gradient has lots of unique colors all over the spectrum, leading to limited options for color reduction, while the SMB3 image is mostly composed of repeating colors.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12557
  • Location: London
Reply with quote
Post Posted: Sat Jan 17, 2015 12:24 pm
Could you add ordered dithers?

It seems to often merge a solid tile with one with a single pixel set, and choose the latter. Can you make it prefer the solid one in this scenario?

Possibly linked to the above, does it give weight to tiles which are used more often?
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sat Jan 17, 2015 3:02 pm
Ordered dithers could be a good idea, specially since it would lead to a smaller amount of not-quite-identical tiles, hopefully increasing the quality of the end result. The original RgbQuant.js didn't come with any ordered dithers, but I guess that functionality could be added without much trouble.

Currently, the tile merging is averaging together the tiles from a cluster and then passing the averaged tiles again through the color reduction; I imagine there are multiple experiments that could be done in order to implement this part, maybe there could be the possibility of doing a weighted averaging by tile popularity, or maybe just pick the most popular tile from each cluster instead of using the average. Another idea would be to use image entropy in order to estimate which tiles are more 'interesting', in order to weight the averages, or even to leave a few of the most interesting tiles untouched..

Basically, there's still room for lots of experimentation. :)
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sun Jan 18, 2015 10:57 pm
New update: Now the merging of similar tiles is weighted by popularity; this improves visuals in large areas of solid color, but the more unique tiles suffer from a quality loss. Maybe I should turn that into a parameter.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Tue Jan 20, 2015 12:35 am
New update:
- Now the tile merging can be weighted by popularity, entropy or both; entropy tends to give greater weight to more detailed tiles, while popularity gives greater weight to tiles that are more common;
- Implemented a few more user-adjustable parameters to the demo application, allowing to change how many tiles will be used, and how the merging will be weighted.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 08 Jul 2001
  • Posts: 8012
  • Location: Paris, France
Reply with quote
Post Posted: Tue Jan 20, 2015 12:59 pm
Interesting.

- One idea would be to allow using 2 palettes (possibly with different number of colours). The algorithm would somehow figure out which palette is best used by which character.

Another idea would be to be able to lock colors into a palette. That is if one want to share palette with sprites. Instead of just reducnig the color count, the availability of unmutable colors can be taken advantage of.

Got beautiful result with 500 tiles and nice dithering with the demo.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Tue Jan 20, 2015 10:03 pm
Bock wrote

- One idea would be to allow using 2 palettes (possibly with different number of colours). The algorithm would somehow figure out which palette is best used by which character.


Finding which palette is the most adequate one shouldn't be too difficult; building the palettes themselves, supposing the user doesn't supply his/her own palettes, would be more complex. There are two ways I imagine this could be implemented by the quantizer:

  • A: Generate a palette for the full tileset, move aside the tiles that are least adequate for the palette, and then compute a new palette for those, or
  • B: Run a clusterization on the tileset to separate the tiles into two clusters, and then generate one palette for each.

I guess I'd have to experiment to see if those would work.

Bock wrote

Another idea would be to be able to lock colors into a palette. That is if one want to share palette with sprites. Instead of just reducnig the color count, the availability of unmutable colors can be taken advantage of.

I guess that could be implemented by prepopulating the color histogram with artificially high color counts for the fixed colors.

Bock wrote

Got beautiful result with 500 tiles and nice dithering with the demo.


Yes, some of the demo images can give pretty nice results, and others, not so much... :P

I guess the demo is already working well enough that it would viable to add support for uploading custom images... I think I'll do that next, before proceeding with more experiments.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Tue Jan 20, 2015 10:55 pm
A new version is available: now, you can provide your own images.
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 407
  • Location: Spain
Reply with quote
Post Posted: Wed Jan 21, 2015 8:33 am
Now i'm getting a javascript error, $orig is not defined
  View user's profile Send private message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Jan 21, 2015 9:40 am
kusfo wrote
Now i'm getting a javascript error, $orig is not defined

That's weird... did you try pressing F5? Which browser are you using?
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 407
  • Location: Spain
Reply with quote
Post Posted: Wed Jan 21, 2015 9:45 am
Chrome in a Mac just now, version 39.0.2171.95 (64-bit)

  View user's profile Send private message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Jan 21, 2015 9:52 am
kusfo wrote
Chrome in a Mac just now, version 39.0.2171.95 (64-bit)

Okay, I'll try testing it on Chrome this afternoon.
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 407
  • Location: Spain
Reply with quote
Post Posted: Wed Jan 21, 2015 10:04 am
It was working yesterday on this computer may it be some change in the code...
  View user's profile Send private message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Jan 21, 2015 2:37 pm
Okay, I've just tested it from a Windows 8 computer:

  • Chrome 39.0.2171.99 m: Works okay.
  • Firefox 35.0: Works okay.
  • IE 10.0.9200.17183: Complains that Math.log2 does not exist.


$orig is a variable that is set through jQuery during the page's load event; it should be pointing to the div that contains the original image; either the 'ready' event (demo.jsm line 240) somehow failed to fire or, somehow, jQuery failed to find $('#orig'); both seem unlikely; unfortunately, the problem doesn't seem to be happening here. :|
I may try testing that on a Windows 7 and a Ubuntu machine when I get back home, to see if it can be reproduced on those.

Did anyone else have problems running it on a Mac?
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 407
  • Location: Spain
Reply with quote
Post Posted: Wed Jan 21, 2015 3:54 pm
It's working on safari.. :-P
  View user's profile Send private message
  • Joined: 26 Jan 2014
  • Posts: 470
Reply with quote
Post Posted: Wed Jan 21, 2015 4:24 pm
haroldoop wrote
A new version is available: now, you can provide your own images.


Thank you for your work. Work perfectly with Firefox Win7.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Jan 21, 2015 10:03 pm
kusfo wrote
It's working on safari.. :-P


That makes it doubly weird. :P

Revo wrote
haroldoop wrote
A new version is available: now, you can provide your own images.


Thank you for your work. Work perfectly with Firefox Win7.


Thanks!

BTW, I've just tested it on my Windows 7 machine:

  • Chrome 39.0.2171.99 m: Works okay.
  • Firefox 35.0: Works okay.
  • IE 11.0.9600.17501: Complains about missing Math.log2


-- edit --

I've also tested it on Firefox 20.0 on Ubuntu 13.04: it complains about missing Math.log2.

-- edit --

Fixed the Math.log2 problems.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sat Jan 24, 2015 2:45 pm
New update: now you can use ordered dithering.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Jan 2015
  • Posts: 2
  • Location: paris
Reply with quote
Post Posted: Sun Jan 25, 2015 12:46 pm
Hi Haroldoop and all !

I written a tool for PC-Engine to convert RGB images to pc-engine format. I built my clustering palette family and pick up some algorithms for dithering.

PC-Engine is a 16 + 15*15 palettes (color 0 is the same for all palettes) from 512 colors.

So I'm very interesting by your work !

Eddy

You can see results from my work on theses forums

www gamopat-forum com/t66680-download-disponible-version-alpha-0-1-91-image2pce

www pcenginefx com/forums/index.php?topic=16282.0

You can download my tool :

somanybits com/i2pce/index.htm

it's still a beta, I must add some functions and improve the render.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sun Jan 25, 2015 1:12 pm
Hello! :)

beddy wrote
Hi Haroldoop and all !

I written a tool for PC-Engine to convert RGB images to pc-engine format. I built my clustering palette family and pick up some algorithms for dithering.

PC-Engine is a 16 + 15*15 palettes (color 0 is the same for all palettes) from 512 colors.

So I'm very interesting by your work !

Eddy

You can see results from my work on theses forums

www gamopat-forum com/t66680-download-disponible-version-alpha-0-1-91-image2pce

www pcenginefx com/forums/index.php?topic=16282.0

You can download my tool :

somanybits com/i2pce/index.htm

it's still a beta, I must add some functions and improve the render.


This PC-Engine tool looks amazing!
I specially like the fact that it can handle multiple palettes.
And the idea of letting the user choose which parts of the image will be dithered and which won't also sound interesting. I was also thinking on doing something similar for RgbQuant-SMS, except it would let the user choose which tiles should be kept unmodified during the tile merging process.

--edit--

I think your tool could be easily be modified to also support SMS, GG or even Sega Genesis; they have very similar palette restrictions:

  • SMS: 16+15 palette, sharing color index 0, from 64 possible colors
  • GG: 16+15 palette, sharing color index 0, from 4096 possible colors
  • Genesis: 16+3*15 palette, sharing color index 0, from 512 possible colors

Just imagine, you could reach an even wider audience! ;)
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 2322
Reply with quote
Post Posted: Sun Jan 25, 2015 2:01 pm
A tool to convert an image for SMS 16+16 colors would be very nice!
It should give the user the option to load a specific secondary (sprite) palette, BTW. (and AFAIR when the sprite palette is used as a secondary background palette -behind sprites- it's a full 16 colors palette... I have to check that anyway)
  View user's profile Send private message Visit poster's website
  • Joined: 25 Jan 2015
  • Posts: 2
  • Location: paris
Reply with quote
Post Posted: Sun Jan 25, 2015 2:07 pm
Tks ;)

Yes it's can be modify this tool easily for others architectures.

I should improve palettes functions (let the user to choose it or load static palette).

In some cases you can see bad effect color with tiles. It's because my cluster function doesn't take tiles neighbors information color. I have an idea to fix it.

it's should be useful to add a little editor to correct manually the final image.

In all cases, I'm not limited about PC-Engine. I'm working on few tools for a lot of architectures.

I'll follow your work ;)
If you have some questions send me an email.

Ed
cloudplane_img2pce.jpg (406.42 KB)
cloudplane_img2pce.jpg

  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Feb 04, 2015 12:14 am
New update: Now you can have multiple palettes per image.
Unfortunately, that feature will be sort of useless until I implement support for exporting the images to an indexed format... :P
  View user's profile Send private message Visit poster's website
  • Joined: 19 Oct 2012
  • Posts: 20
Reply with quote
Post Posted: Wed Feb 04, 2015 6:06 pm
This is really nice and useful, thanks!

I have one question though: when reducing tiles, the algorithm seems to be relatively indeterministic (as in, when running it twice with the same image and the same set of parameters you get different results). Is there a way to configure it that you get the same result each time?

Reason I ask is 'cause I'm investigating the possibility of using this to implement lossy compression for FMV/animations. Here, re-use of tiles between frames would be greatly helped if the reduction algorithm behave deterministically for the same image (and preferably for very similar images as well, but that's not your problem :) ).
  View user's profile Send private message
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Feb 04, 2015 9:35 pm
TheMole wrote
This is really nice and useful, thanks!

You're welcome! :)

TheMole wrote

I have one question though: when reducing tiles, the algorithm seems to be relatively indeterministic (as in, when running it twice with the same image and the same set of parameters you get different results). Is there a way to configure it that you get the same result each time?


I guess the indeterministic results are because of the tile clusterization step; I'm not seeding the k-means algorithm with predefined centroids and, as a result, it's seeding itself with random ones; seeding the clusterizer with non-random data should be enough to create repeatable results. I haven't implemented that feature yet, but it should be easy to implement.

TheMole wrote

Reason I ask is 'cause I'm investigating the possibility of using this to implement lossy compression for FMV/animations. Here, re-use of tiles between frames would be greatly helped if the reduction algorithm behave deterministically for the same image (and preferably for very similar images as well, but that's not your problem :) ).


Sounds like a very interesting idea. One easy way to use this tool to optimize a video would be to treat all the frames as a single giant image, though the optimization in this case would consume quite a lot of memory; one less expensive alternative would be to process a limited number of frames at a time, just like many video codecs make use of keyframes. Yet another alternative would be to reduce the tile count of each frame individually in order to ensure none of them individually crosses the maximum tile count per frame, and them merge together the tilesets of all the reduced frames, so as to ensure the video uses as few tiles as possible.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12557
  • Location: London
Reply with quote
Post Posted: Wed Feb 04, 2015 10:40 pm
I've been thinking of videos too. What you really want to do is to take the existing tileset for the preceding frame and figure out an optimal modification to make to it to match the next, even better if you can weight it to avoid destroying data needed for later frames. Factor in some estimation of the work involved for these modifications and the limited time per frame to make them, and you have a quite tricky problem. You can also be thinking of modifying unused tiles during the active display...
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Thu Feb 05, 2015 12:46 am
Okay, now I've just modified the clusterization to be non-random.
  View user's profile Send private message Visit poster's website
  • Joined: 19 Oct 2012
  • Posts: 20
Reply with quote
Post Posted: Thu Feb 05, 2015 8:54 am
haroldoop wrote
Okay, now I've just modified the clusterization to be non-random.


Cool, thanks!
  View user's profile Send private message
  • Joined: 19 Oct 2012
  • Posts: 20
Reply with quote
Post Posted: Thu Feb 05, 2015 9:01 am
haroldoop wrote
Sounds like a very interesting idea. One easy way to use this tool to optimize a video would be to treat all the frames as a single giant image, though the optimization in this case would consume quite a lot of memory; one less expensive alternative would be to process a limited number of frames at a time, just like many video codecs make use of keyframes.


That's exactly what I had planned on doing: put a bunch of frames together in a single image (with solid 8-pixel borders between them) and have them all work from the same set of tiles; and repeat that for the entire clip.

I'm doing a Bad Apple port (although not for the SMS but the TI-99/4A, which only supports the legacy SMS modes), so my source material really helps in achieving good compression results with a simple decompression algorithm on the target.
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 2322
Reply with quote
Post Posted: Thu Jan 19, 2017 3:36 pm
this for some reason no longer works (stops before reducing tiles count) :(
Quote
TypeError: dithKern.contains is not a function

can you fix that?
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Thu Jan 19, 2017 7:33 pm
sverx wrote
this for some reason no longer works (stops before reducing tiles count) :(
Quote
TypeError: dithKern.contains is not a function

can you fix that?


Silly me.. String.prototype.contains() was a deprecated function... :P

It should be a simple enough fix. I'll get into it as soon as I arrive home.

--- edit ---

Okay, it's corrected. Now, it should work okay both with and without dithering.
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 2322
Reply with quote
Post Posted: Fri Jan 20, 2017 9:10 am
Thanks! It works :)
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12557
  • Location: London
Reply with quote
Post Posted: Tue Feb 05, 2019 8:12 pm
Resurrecting this, I just noticed this doesn't do tile mirroring optimisations. Could you add that? I've used the "playground" quite a lot to help me massage tile counts down...
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Tue Feb 05, 2019 8:21 pm
Maxim wrote
Resurrecting this, I just noticed this doesn't do tile mirroring optimisations. Could you add that? I've used the "playground" quite a lot to help me massage tile counts down...

That's weird.. it's designed to support tile mirroring; I will take a look at that as soon as I get home.[/list]
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12557
  • Location: London
Reply with quote
Post Posted: Tue Feb 05, 2019 8:25 pm
It seems to be a bit inconsistent. I was using an image which was already made for SMS, just with too high tile count, and it was doing some weird substitutions in places where the tile is an exact mirror of one elsewhere. In other places it is clearly using mirrored tiles. Image is attached. I was reducing to 387 tiles with no dithering. The top-left dithered tile gets swapped for a blank one instead of a mirror of the tiles to its right. It also reports 444 tiles before optimisation - there are 442 after mirroring optimisation, but maybe it's not trying to do that at this stage.
Intro 01.png (7.24 KB)
Intro 01.png

  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Tue Feb 05, 2019 10:39 pm
Maxim wrote
It seems to be a bit inconsistent. I was using an image which was already made for SMS, just with too high tile count, and it was doing some weird substitutions in places where the tile is an exact mirror of one elsewhere. In other places it is clearly using mirrored tiles. Image is attached. I was reducing to 387 tiles with no dithering. The top-left dithered tile gets swapped for a blank one instead of a mirror of the tiles to its right. It also reports 444 tiles before optimisation - there are 442 after mirroring optimisation, but maybe it's not trying to do that at this stage.


Thanks for the example; I have tested the image with default options, with 256 tiles (the default), 444 tiles (the amount of tiles in the image after removing duplicated/flipped images) and 128 tiles; please see results below.

-- edit --

I have also tested it with a minimal, perfectly simmetrical, 16x16 image; it seems the program is actually failing to detect some edge cases. The tilecount should have been reduced to 1 right on the first step, but it isn't, and it is also failing to flip the tile correctly at the last step.
01 - 256 tiles.png (83.65 KB)
256 tiles
01 - 256 tiles.png
02 - 444 tiles.png (87.37 KB)
444 tiles
02 - 444 tiles.png
03 - 128 tiles.png (428.65 KB)
128 tiles
03 - 128 tiles.png
04 - Minimal.png (23.22 KB)
Minimal test
04 - Minimal.png

  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12557
  • Location: London
Reply with quote
Post Posted: Wed Feb 06, 2019 6:35 am
I think the minimal case is demonstrating it better than my example.
  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 520
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Wed Feb 06, 2019 9:43 pm
Maxim wrote
I think the minimal case is demonstrating it better than my example.


OK, I have fixed the tile flipping problem; the duplicate tile detection was considering the flipping with no problems, but was failing to consider that some tiles should just be left unflipped! :P

Anyway, that one bug is now out of the way. Please, try accessing the RgbQuant-SMS.js page, and pressing Ctrl+F5 to refresh the browser cache. The tool should be working much better now.

Thanks for the bug report! ;)
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 2322
Reply with quote
Post Posted: Thu Feb 07, 2019 12:39 pm
one small thing still: number of "Tiles w/o similars" is set at maxTiles even when number of "Tileset w/o dups" is lower.
  View user's profile Send private message Visit poster's website
Reply to topic



Back to the top of this page

Back to SMS Power!