Tools for converting RGB images to fixed-palette indexed (w/ lots of comparison pics)

This is as much a rant as anything else, but I've recently come to the conclusion that GIMP sucks for converting truecolour images into indexed/paletted ones, at least using nearest colour matching. I guess this means I'm going to go try a bunch of different graphics programs.

PSP9 seems pretty good, SLADE is OK but also tends to give very "flat" results IMHO, ZDoom's colour mapping is usually good but a bit weird and not exactly the easiest tool to work with images anyhow.
edit: I take it back about SLADE, it produces near-identical results to PSP9.

Someone in another thread with high-res weapon sprites recommended Irfanview which I guess I will try next.

Anyhow else got any (preferably free) recommendations? Anyone interested in seeing some comparison shots?

I'm surprised to read that various programs can produce noticeably different results. It would be interesting to see some examples.

I thought that RGB->palette conversions will be bad looking always and unavoidably, if the image wasn't given special care by hand with the palette in mind. I've always been using GIMP, and fixed bad-looking colours by hand if needed be. Never worked with anything elaborate, mostly just simple texture edits / rescales that needed conversion to RGB and then back. I wonder how a program could manage this better than GIMP does.

plums said:

This is as much a rant as anything else, but I've recently come to the conclusion that GIMP sucks for converting truecolour images into indexed/paletted ones. Someone in another thread with high-res weapon sprites recommended Irfanview which I guess I will try next.

Anyhow else got any (preferably free) recommendations? Anyone interested in seeing some comparison shots?

The gimp is perfect :

A - load the RGB image into the gimp.
B - Menus ; image -> mode -> indexed.
C - Then give aprocimately 40 to 100 colors max in the text-box.
D - Choose positioned dithering in the last dropbox.
C - BAM. high quality color indexing.

Rgb Full color ;
http://i.imgur.com/NF2yP3p.png

Indexed 40 colors with the gimp ;
http://i.imgur.com/h3t8rwb.png

All that is needed now is to manualy fix the few stray pixels on the pants and its done.
You can never do this without having to fix a pixel here or there, a computer is not a human eye and brain (yet).

The way I would convert images to a palette back in the day would be to make a 2-layer version of it in a graphics program. I'd have one layer be converted by a "nearest match" sort of algorithm, and the other layer use a dithering algorithm. Then I'd basically erase parts where I thought one or the other method looked better for that graphic and merge it that way.

Thanks guys but I should have been more specific, I'm pretty knowledgeable about using different techniques for reducing colours. Sometimes there are certain things that you absolutely can't dither though, e.g. COLORMAPs. And of course I mean to work with fixed palettes like the ones in Doom already, not arbitrary ones - I have a feeling that GIMP's colour-indexing algorithms might fare better when it gets to pick its own palette.

I'll post some comparison shots soon, but for now:

• Paint Shop Pro 9 and SLADE produce virtually identical results, and seem to be the best general purpose algorithms overall. I imagine they're also the simplest.
  
• mtPaint produces results completely different from other programs, sometimes they look good and sometimes not so much.
  
• ZDoom is similar to PSP9/slade, but with more visible banding in some spots. It's also entirely unsuited to outputting images, but if it were really good I guess someone could take the algorithm it uses and turn it into a standalone program or whatever.
  
• ImageMagick and IrfanView do OK, but also a lot of visible banding. I probably won't keep IrfanView around just for colour reduction.
  
• The GIMP is pretty rough and seems to make some strange decisions about what colour is the closest match at times. I imagine it's got a weighted algorithm (not giving each of R, G, and B values equal worth), and that maybe works best when it can pick its own final palette.
  
• I couldn't figure out how to get Grafx to reduce a 32 bit image to a preexisting palette.

I'm often messing around with pygame and image stuff, but what exactly do you want the program to do? Like input an image then round each pixel to the nearest rgb color in the doom palette?:
http://zdoom.org/wiki/palette

Yeah, I'm playing around with different programs that do that because they produce different results. Like here's 3 pictures of my buddy D'Sparil; the first is his native Heretic palette, the second in Doom palette using GIMP to convert it, and the 3rd in Doom palette using Paint Shop Pro 9 to convert. You might have to zoom in to see the difference but the PSP9 one looks a lot better than the GIMP one to me. It's got a lot more colour depth and fewer hard edges between colours.



It basically started out as an attempt to make a better TINTTAB for Heretic translucency and now I've gone full nerd and started making comparisons for different programs and algorithms...

Anyhow if pygame has a built-in algorithm to do that and you can make a quick program to convert images, or you want to go nuts and code an algorithm yourself, be my guest. Certainly not needed though. BTW is that what you use for those forum avatars?

Its interesting to look at those side by side. They all look good at first glance to me. Only after staring for like a minute do I notice something like the doom palette one having a fairly large solid color lighter green blotch above the nose whereas the first is smoother. But maybe the doom palette simply lacks enough shades of green to do it any better (not sure). Then it took like 4 minutes of staring to notice anything significant between the 2nd and 3rd (shoulders of D'Sparil have yellowy blotches in the 2nd). Maybe the difference is just one algorithm rounds a decimal and the other just cuts off to an integer or something.

I make the avatars w/ pygame but am no coding expert. However maybe some bloatware programs do all kinds of anti aliasing and whatever else under the hood (not sure) so a simple pixel based program without bells/whistles might have an advantage. I might try to round the 1st image into dooms palette or whatever (hopefully extracting the rgb triplets from the wiki color palette pic would work without some complicated problem changing the values on me.. would be easier to have a list of the rgb triplets to begin with).

One possible algorithm could make a 'fake' intermediate color (if the palette doesn't have enough) by checkerboarding the pixels of 2 colors into 1 color. Or every pixel could check all its neighbors values and average to them or something.

Comparison pictures

Here's a few pictures converted into Doom (or Heretic in the first case) palettes using "Nearest Colour" approximation. I'll probably do various kinds of dithers tomorrow, just for fun.

Unfortunately the DW forums have a pretty small limit on the number of images in a post, so I'm just including them as links instead. :( All images can be downloaded in a zip, if you prefer: https://www.mediafire.com/?xsb01wx3slnpoju

Programs tested: The GIMP 2.8.10, i.mage, IrfanView, ImageMagick, mtPaint, pngnq-s9, Paint Shop Pro 9, SLADE 3(only for the first one, produces images ~identical to PSP9), ZDoom (only for the first one, too hard to work with - put the image into a wad as a texture in HI_START/HI_END lumps, went fullbright, took a screenshot. Ugh!).

My personal opinion is that mtPaint and PSP9 produce the best images, with pngnq-s9 being quite good as well. mtPaint seems to good give colour depth, which is often more important than matching each colour independent of others. IrfanView and i.mage do ok jobs, and might be better in some circumstances. ImageMagick isn't great, and GIMP is generally the worst. But judge for yourself!



Heretic TINTTAB, or the straw that broke the camel's back.

I was playing around with making a new TINTTAB (the colour translation lump for calculating transparency) for Heretic, just to see if I could get any better results than the one in the iwad. In fact what I got with the GIMP was much worse. I've had issues with GIMP's nearest colour matching before, but this one looked bad enough to make me start looking at what other programs can do.

iwad TINTTAB
http://i.imgur.com/i64u04i.png

24-bit recreation


The 24-bit version was created by taking Heretic's palette as a 256x1 image, tiling it to be a 256px square, then duplicating that layer, flipping it around, and setting it to 60% opacity. 60% was just an approximation, but it turned out to be quite close: Paint Shop Pro 9 gave almost the same image as the iwad version when converting. I suspect that PSP9 uses a fairly simple algorithm and with the right opacity would produce the same image as the iwad lump.

GIMP


i.mage


IrfanView


ImageMagick


mtPaint


pngnq-s9


Paint Shop Pro 9


ZDoom


SLADE - same as PSP9
http://i.imgur.com/TVbsznL.png


edit: Other comparison shots moved to posts below!

gggmork said:

Its interesting to look at those side by side. They all look good at first glance to me.

Part of the problem is that with such small images, details are hard to notice when posted on a modern monitor. When the image is taking up your whole screen, it's a lot easier to see.

would be easier to have a list of the rgb triplets to begin with

Give me a minute and I'll post them.

One possible algorithm could make a 'fake' intermediate color (if the palette doesn't have enough) by checkerboarding the pixels of 2 colors into 1 color. Or every pixel could check all its neighbors values and average to them or something.

That's actually what dithering is, at least ordered dithering. Tons of algorithms for it, and some give decent results. But again there's the problem of something looking good at small resolution but crappy at Doom fullscreen resolution, and it doesn't work for stuff like the TINTTAB thing because each pixel is important since it's not an "image" in the traditional sense but a lookup table.

edit: Actually it would be really cool if a program only dithered when there wasn't a match beyond a certain threshold, so the closely-matching colours got remapped without dithering. This is a bit like what Linguica was talking about, except it would be automatic.

Doom colour triples in decimal format. PSP9's palettes are basically just this plus a header, so it's not hard to make.

10 pics per post, that's enough to do one comparison per post.

D'Sparil, converted from Heretic to Doom palette. Enlarged to show detail.


I find the best way to remap colours from other fixed-paletted games is to make your own translation map in SLADE, which I haven't done here. (Maybe I should have?) Nonetheless it's a good test case.

GIMP


i.mage


IrfanView


ImageMagick


mtPaint


pngnq-s9


Paint Shop Pro 9

Colour gradients


GIMP


i.mage


IrfanView


ImageMagick


mtPaint


pngnq-s9


Paint Shop Pro 9

Rocky mountains


Intentionally chosen for its light blue sky, which Doom can't really approximate. Some programs add some blue where it looks quite bad, but in this case it's an easy fix manually, and so I'd look for other parts of the image in determining the best one.

GIMP


i.mage


IrfanView


ImageMagick


mtPaint


pngnq-s9


Paint Shop Pro 9

SLADE's color matching is fully customizable!

Look in the Colorimetry tab of the Preferences panel.

Personally I have found out that what works best, at least for Doom, is to stay in the RGB space, but you can choose between making the computations with integers or double-precision floats. The use of floats may explain why there's less banding than in ZDoom, because the algorithm is otherwise the same.

It is also possible to operate in HSL space, and colors are converted to HSL before matching. Then you have various CIE colorspaces. I have found out that, despite their complexity, the results they provide isn't very satisfying. I believe CIEDE 2000, the latest and supposedly best, is the one that's used by GIMP.

SLADE also allows you to define factors for everything. If you want RGB matching but blue matches are more important, increase the B factor.

Anyway, default values are probably best in any case, and if you experiment a bit don't forget to reset to default after you're done.

Gez said:

SLADE's color matching is fully customizable!

Wow! I missed that entirely. Will definitely play around with that.

Does it affect anything other than image conversion? (COLORMAP generation, Colorize/Tint, maybe other things?)

Also, I know you can generate COLORMAPs from palettes, is there any way to generate extra maps like TINTTAB?

plums said:

Does it affect anything other than image conversion? (COLORMAP generation, Colorize/Tint, maybe other things?)

It affects everything where color matching is used, so yes.

plums said:

Also, I know you can generate COLORMAPs from palettes, is there any way to generate extra maps like TINTTAB?

Not at the moment, no. Generating a translucency table is a good idea, I'll see if I can add this.

Tools I'm familiar with.

Photoshop CS4:


Photoshop CS4, 40% diffusion:


It also has different dithering algorithms, but they're too noisy for small images.

XWE:


Photoshop CS4 (we're using Doom palette, right?):


XWE:


Photoshop CS4:


XWE:


I don't know how it managed to shove cyan there. I think it did that on exporting rather than while converting.

Photoshop CS4:


Photoshop CS4, 70% diffusion:


Ugh. Blues were always the hardest to work with.

XWE:


SLADE's features sound pretty cool. I need to check them out.

gggmork said:

Only after staring for like a minute do I notice something like the doom palette one having a fairly large solid color lighter green blotch above the nose whereas the first is smoother. But maybe the doom palette simply lacks enough shades of green to do it any better (not sure).

Every palette conversion will lead to data loss. There'll be less unique colors in your image with each iteration. It's a bit like compression - the best way is to convert from the source image whenever possible.

Da Werecat said:

Photoshop CS4 (we're using Doom palette, right?)
http://i.imgur.com/qURehmF.png

The TINTTAB square (this image) uses the Heretic palette, since its purpose is translucency for Heretic. All others use Doom's.

Thanks for the extra shots! I was hoping a PS user would be able to supply some. CS4 diffusion looks quite decent on D'Sparil, is the diffusion amount adjustable?

Every palette conversion will lead to data loss. There'll be less unique colors in your image with each iteration.

Not necessarily, if your intent is to preserve colour depth at all costs. I'll do a manual-remapped version of D'Sparil tomorrow if no one beats me to it.

Will also make a bunch with dithering, later. AFAIK SLADE has no dithering options, though it evidently wouldn't be the first time I missed a feature in SLADE.

plums said:

The TINTTAB square (this image) uses the Heretic palette, since its purpose is translucency for Heretic.

I'm not sure why now, but I thought that you used Doom palette anyway.

Shop:


XWE:


BONUS FEATURE! How XWE treats indexed color PNGs.

Original image in Heretic palette -> XWE using Doom palette:


Original image in Heretic palette -> XWE using Heretic palette:


Quantized to Doom palette in Photoshop -> XWE using Doom palette:


True color PNGs are being properly converted.

CS4 diffusion looks quite decent on D'Sparil, is the diffusion amount adjustable?

Yep.

But I'm trying not to rely on dithering too much.

This is just my first try and I'm just guessing what to do as I go (my first fail attempt was more lol because I got the rgb 'average' like (r+g+b)/3... then chose the one where that average was closest to the source color's average... but dumb idea because like red and green would both have the same average.... (255+0+0)/3 is same as (0+255+0)/3)

So this is the specific algorithm for this one:
get 'red distance' between each palette color and original color
like if original color red is 42 is and palette red is 46, red distance is 4 (or if orig red is 42 and pal red is 40, red dist is 2 since it takes absolute value of one minus the other)
Then for each palette color go: redDistance+greenDistance+blueDistance.. and that's the overall distance. Now just sort those overall distances to find the one with the lowest overall distance and choose that color. (if more than one had equal distances I just chose the leftmost one that the sort produced)

Not sure if it looks better/worse to you (the last pic obviously), just my first attempt and you can see what a specific simple algorithm produces with no extra under the hood shenanigans (I did change from png to bmp at one point to try to remove per pixel alpha crap but doubt that changed anything):

By the way, I found it odd that the doom palette has these duplicates:
duplicates= [[67, 0, 0], [0, 0, 0], [255, 255, 255], [0, 0, 83], [79, 0, 0]]
(they each appear twice, except 255,255,255 which appears 4 times. My guess is like maybe 0,0,0 is considered 'dark blue' and also 'dark green' or something, then other complex light changing stuff handles them according to their intended color even though they're the same.

gggmork said:

This is just my first try and I'm just guessing what to do as I go (my first fail attempt was more lol because I got the rgb 'average' like (r+g+b)/3... then chose the one where that average was closest to the source color's average... but dumb idea because like red and green would both have the same average.... (255+0+0)/3 is same as (0+255+0)/3)

So this is the specific algorithm for this one:
get 'red distance' between each palette color and original color
like if original color red is 42 is and palette red is 46, red distance is 4 (or if orig red is 42 and pal red is 40, red dist is 2 since it takes absolute value of one minus the other)
Then for each palette color go: redDistance+greenDistance+blueDistance.. and that's the overall distance. Now just sort those overall distances to find the one with the lowest overall distance and choose that color. (if more than one had equal distances I just chose the leftmost one that the sort produced)

If you want the distance, you need to square stuff up.

You know how the length of the hypotenuse squared is equal to the sum of the squared lengths of the other two sides? And you know how Cartesian coordinates (x, y pairs) can be thought of as a right angle triangle, with one point at [0, 0], one at [x, 0], and one at [x, y] (or alternative, [0, 0], [0, y], [x, y] works too). So you square x, you square y, you make the sum, and then you extract the square root of that sum and you have the distance between [0, 0] and [x, y].

If you just want to compare distances, you can skip the last part. Just square both sides, then make the sum. If the sum is greater, the root will be greater too, so for simple comparisons you don't need to go further.

And for a 3D cartesian coordinates, you do the same thing, but in three dimensions: x²+y²+z².

So the distance squared between two colors in RGB space:
r = abs(r1 - r2)
g = abs(g1 - g2)
b = abs(b1 - b2)
ds = r²+g²+b²

Find the color in the palette with the smallest ds. If ds is 0, you know you have a perfect match.


With SLADE 3 there's the subtlety that if you want, you can give different weights to stuff. Normally r, g, and b all have the same weight, but if you want green to have a weight of five, then the computation will be r²+5g²+b².

It works the same for HSV, HSL, or LAB. Find distance between two points. Optionally make some dimensions cost more than others (kind of like stretching the size of the image unevenly.)

That worked much better, thanks:

The rightmost one did that and looks better than the rest imo (the first is the original heretic source image used).

I never thought to treat a rgb color as a 3d point (one thought is the '3d point distance' between 2 rgbs could be greater than 255 I think, which is the max rgb value, which doesn't matter in this algorithm at least). I wonder why my amateur program output (last pic) looks better than the 2nd and 3rd which came from 'professional' programs. I did loop through the final pic to make sure each pixel was in the doom palette to make sure I didn't do something dumb and they all were.

gggmork said:

That worked much better, thanks:
http://i.imgur.com/8lViMfY.png
The rightmost one did that and looks better than the rest imo (the first is the original heretic source image used).

Enlarged version for comparison:


That looks really good, it's extremely close to the one from mtPaint which is the best of the ones I posted for D'Sparil. I had to compare them in GIMP with one as a difference layer to even tell if there was a difference at all.

also

By the way, I found it odd that the doom palette has these duplicates:
duplicates= [[67, 0, 0], [0, 0, 0], [255, 255, 255], [0, 0, 83], [79, 0, 0]]

There's a lot of redundancy in the Doom palette, you could get rid of it entirely if you remapped all the graphics etc. I think it just comes from old paint tools where you have sequences of colours as a sort of "mini-palette" which makes freehand drawing easier or something? I forget what program id used to make Doom graphics but here's a shot of Grafx2, having the colours in some order makes it easier to work with and do things like gradients etc.

Interesting to see such a variation in performance across different tools. i.mage's conversion of the Hexen sprite looks like the best of the bunch so far. I'd suggest that testing on real sprites is the best approach, and trying to convert rainbow pictures like TINTTAB is not helpful and at worst misleading: no matter what algorithm you use, you're always going to be limited to the palette that you're converting to, so this isn't a fair test.

We had some problems with palettization for Freedoom a few months back that were never really resolved so this might be worth looking at.

In the end it's a difficult problem and nothing really beats just designing for the intended palette in the first place. But in the past I've wonder if some kind of human-guided palettization tool would be useful: something that will do palettization in real time, show you the results and let you adjust the original image (eg. adjusting particular ranges of colors) to help get something that looks nice.

fraggle said:

i.mage's conversion of the Hexen sprite looks like the best of the bunch so far.

The forehead is very good, but the legs are among the worst.

By the way looping through each pixel and getting the average r/g/b values from itself and its 8 neighbors, instead of itself only, then doing the same just makes it blurry:


What I don't really get is there's really only 1 main algorithm to do this (at least when you know the right one like gez and not retarded like me) so why so many different outputs? My guess is these bigger programs optimize algorithms so they work faster at the expense of being less perfect. Because per pixel stuff can be slow (definitely in python/pygame)

The legs are bad, but then the contrast in the back of the serpent is better. Ultimately there's no perfect solution with automatic conversion.

fraggle said:

I'd suggest that testing on real sprites is the best approach, and trying to convert rainbow pictures like TINTTAB is not helpful and at worst misleading: no matter what algorithm you use, you're always going to be limited to the palette that you're converting to, so this isn't a fair test.

TINTTAB is a bad general-purpose test, I agree. But it's far from just a theoretical test-case: I was actually hoping to get a better (less banded/desaturated) TINTTAB to use in Heretic, which is what set me off on this whole comparison. (Actually it was a problem that Crispy Doom has about blue transparency being mapped to grey that really started it.) But even then, it's hard to just look at the image and get a fair sense of how it looks when used as a lookup table in-game.

gggmork said:

What I don't really get is there's really only 1 main algorithm to do this (at least when you know the right one like gez and not retarded like me) so why so many different outputs? My guess is these bigger programs optimize algorithms so they work faster at the expense of being less perfect. Because per pixel stuff can be slow (definitely in python/pygame)

Don't think it's optimizations, because simple additions and multiplications are done very fast (remember, you don't need to get the root at the end since you can use the squared distance instead of the distance).

Instead, differences can be explained by:
1. Different color matching algorithms. Look at the complexity of the CIE algorithms.
2. Processing the image per region, instead of pixel per pixel. Any sort of dithering, for instance.

Either way, you're adding complexity in the color conversion process, not optimization. With the kind of resolution that Doom images tend to have (maximum dimensions 320x200 in vanilla), it doesn't really matter.