Feel free to fix -- my time is pretty much gone.  I *do* feel that this,
as a new feature should be 1.3 material though, and hence should
probably be waiting on the new quant landing (Raphaël, I can give
you a copy of the convert.c etc stuff from my tree if you want a
head-start, but I can't promise anything about its compilability,
speed or quality right now).

I was about to assert that this would be very easy to implement, but
after a little thinking I'm now rather more sure that to use only
colours which are present in the image (and the best ones, at that)
you'd have to sidestep the whole box-cut quantization which is really
not friendly to such a concept.

One relatively painless method/hack would be to add yet another pass
over the image data which snaps all of the colours in the final
palette back to their closest in-image colour before doing the final
remap or dither.  Yeah, that's probably how I'd end up doing it.

What I had in mind was to implement a quick patch for 1.2.x and leave
the better solution for 1.3.x.  And yes, the solution that I was
thinking about is similar to yours: after the first pass that
generates the optimal palette, snap all colors^H^Hours back to
something that exists in the original image and then do the last pass
over the image to convert to indexed mode (with or without dithering).

The solution for the 1.3 branch (and all future versions) could be
different and would be based on your new quantization routines.  Alas
I do not have a working 1.3 tree for the moment, because of some CVS
access problems on my side (should be solved in a couple of weeks).

FYI: The new quant code is still box-cut based so it probably won't be
any easier (or harder) to do it 'right' there.

Is another workaround to index using the Web palette (or some other
user defined palette where we keep our desired colours) rather than
the optimum palette?

I'm not sure if it's possible to define a partial palette and say "use
this palette, filling in the rest of the colours up to a max of 25[56]
with whatever's best" - that would, I think, be the optimum solution.

Cheers,
Dave.

That suggestion is, of course, exactly the same as the one discussed
in http://bugzilla.gnome.org/show_bug.cgi?id=66258

Dave.

The problem described here is different than the one mentioned in
bug #66258.  I took the web palette as an example in the original
description, but this was only an example (which could be partially
solved by the proposal that I wrote in bug #66258, but this is not
a general solution to the problem described here).  The goal is to
generate an optimal color palette while preserving the original RGB
values of some or all of the colors that are present in the original
image.

For example, if the original image contained pure white (#ffffff) and
pure black (#000000), the generated color palette should contain
these colors instead of something like #fdfdfd and #020202.  This
means that the error vector will be larger for the colors that do not
fit in the palette, but it will be zero for the colors that are in
the palette and this is desirable in some cases.

The "partial palette, with optimised selection for the bits we don't
care about" is the suggestion I was referring to -not the use of
custom palettes.

Dave.

This seems to be an enhancement request and should be labelled as
such, or am I wrong ?

Well, from my point of view it is a bug, especially with colors like
pure white and pure black that are modified during the conversion.
This is an annoying bug because you have no way to prevent it, except
by doing the conversion in several steps as described above.  Some
other programs do not behave in that way and try to preserve some
or all of the colors that are present in the original image (I do not
remember which program I tried some time ago - maybe Photoshop or PSP).
Anyway, I will switch this to "enhancement" if you prefer this.

Changes at the request of Dave Neary on the developer mailing list.  
I am changing many of the bugzilla reports that have not specified a target
milestone to Future milestone.  Hope that is acceptable.  

I consider this an important feature. It's needed a lot for CI and web
work.

Are the colours changed when you turn off dithering? I don't believe
they should be... and if you're using dithering it's expected behaviour.

In any case, it's a bug rather than a feature request. Changing
milestone to 2.0.

Cheers,
Dave.

I'm pretty sure that this works as designed.  If you ask for colour
reduction then colours will be reduced, by fair means or foul --
squeezing a quart into a pint pot is not a lossless process.  I don't
know quite what you expect.

That's not a bug, it's the quantization process by which colour (or
other vector) reduction most often works.  Think lossy compression. 
By dint of effort and special-casing, we do losslessly handle the
'reduction' process when there's no reduction to be done, which then
just becomes a matter of counting and hashing.  Most quantizers aren't
that considerate...

I think that comment 4 is actually pretty much the proper way to
implement this *new feature*.

*** Bug 121076 has been marked as a duplicate of this bug. ***

Suggesting WONTFIX. Bumping milestone to Future.

Dave.

It seems sort of dead now, but I hope this won't end as WONTFIX.

Dave: Yes, colors do change when dithering is turned off (easy to demonstrate).

And IMHO this is a bug, if something that renders a tool unusable in many common
cases (namely optimization for web) is a bug.

Adam: It can change white to nonwhite on images that have 90% of pure white,
some black antialiased to white, and some some other color aintialiased to
white, nothing else (can attach example).  And yes, I can see the change and it
looks particularly ugly when you put several such images with [differently]
distorted white in a row; ideally on a common white background. The same usually
happens with dialog screenshots, where the dominant gray end up as quite a
different color. This is not what I expect.

So what do I expect? I expect that if a single color fills a considerable part
of the image, then this particular color is preserved exactly. Simple. What a
considerable part is, it generally depends on the target number of colors, but
changing a color that forms 90% of the image when quantizing to 256 colors is
not acceptable.

I suppose exact preservation of colors with very high counts may not be easy to
implant into the current algorithm, and it probably will have to be optional, as
photographs have different quantization requirements than lineart, morover one
normally wants this only if not dithering. But now, GIMP is not usable for
lineart quantization.

Created attachment 29870 [details]
Test case

The attached image consists 99% of pure white. Quantization to 256 colors,
optimal (pah!) palette, no dithering, changes the white to #fefffc.

I think we thoroughly established some years ago that this is not ideal behaviour.

So far we've got lots of suggestions. I'll try to summarize and maybe we can
figure out how this could be implemented.

I think, it boils down to a single checkbox in the dialog when converting using
a custom palette: [x] Add colors as needed

This way, I can use the palette I used for creating the image (or simply create
a palette containing all the important colors) and have them preserved while 
still allowing for additional colors to be used (e.g. blends of these colors 
created by aliasing, gradients etc.).

I don't know about quantization algorithms but I guess that the algorithm could
be modified to either
- add the fixed colors before more colors are choosen automatically
- decrease the number of available colors by the number of fixed colors; do not
  take the fixed colors into account for determining the optimal colors and
  simply add them afterwards before doing the actual conversion

I suppose that the second approach is easier to implement and wouldn't alter the
existing code too much (it's basically an implementation of the second
workaround suggested in the bugreport).

Adam: I'm not sure what you refer to, but you are right anyway ;-) IMHO general
ideal quantizer doesn't exist. The problem is that I often need the other
nonideal behaviour.

Tino: Your suggestion has the problem I don't want to create a custom palette of
important colors for each image I convert to indexed. I'd still have to write a
poor man's quantizer that only finds the important colors (probably colors with
very high counts, maybe filling continuous areas in addition, maybe some other
critetion), creates a palette from them, and then leaves the hard work on the
normal quantizer.

For example, in the attached example it's clear -- for a human -- that white,
black, and red should be preserved exactly. By adding another six gray and red
tones I was able to manually create a palette leading to a quantized image
hardly distinguishable from the original -- something GIMP currently can't do
with 256 colors. There must be some way how to teach the machine to do it too.

Wait, are we still talking about gimp < 2.0 ?

I talk about Gimp 2.0.x (any), don't have 1.2 any more. I'm sorry for confusion.

The descriptions of bug #66257 (this one) and bug #66258 make it difficult to
distinguish them. According to their titles, this one complains that there are
colors that are changed during the conversion (this is not a bug, since as noted
by Adam in comment #14 per the pigeonhole principle it's impossible that all of
the colors stay the same), and the next one says that some colors should not be
modified. I can hardly see the difference except by comment #17 which seems to
suggest here that predominant colors be kept.

My suggestion is that the checkbox for this report should be called something in
the line of "[x] Keep predominant colors", perhaps with a Threshold setting in %
of coverage, leaving Tino's suggestion from comment #20 for the next. If Raphael
and Yeti agree, I think that the descriptions should be adjusted accordingly.

Since it's impossible that all colors are kept whenever the image has more than
256, one way of selecting manually which colors should stay the same is to
create a palette out of them, but that's left for bug #66258. Perhaps a quick
palette creation method by means of picking colors from the image could be that
bug's companion. If anyone else can figure out how to let gimp know what the
corporate colors of an enterprise are, suggestons are welcome.

So the user interface would end up like this:

()Generate optimum palette     Max colors: [ 256]
()Use black and white palette
()Use custom palette   [         Web          ]
    []Remove unused colors
    []Add colors as needed     Max colors: [ 256]   /* as per bug #66258 */
[]Keep Predominant Colors      Threshold:  [  20]%  /* as per this one */

The last option would be grayed if the "Use black and white palette" option is
checked.

I seriously wonder why anyone would want to put so much effort into indexed
colormaps. Why would you want to use them nowadays? IMO indexed support should
better be dropped from the GIMP core in a not too distant future.

Because indexed PNGs can be 3x smaller with little visible difference? Because
some special applications require it?

While I don't _draw_ indexed images often (though I still do it sometimes), I
definitely want to _convert_ to them -- and that's what this thread is about.
You are going to upset a lot of people by removing the possibility.

adam: Indexed code hasn't changed at all since 1.2, so there's nothing specific
to 2.0 in here.

Sven: People use indexed mode. For gifs and for indexed pngs. Just saying that
the mode sucks and no-one should use it doesn't change that. And dropping it
from the core would be a bad thing to do. I am sure that there will be demand
for an indexed mode in gegl (or at the very least, an op that handles indexing
to provide biotmaps suitable for saving as indexed png and gif.

> adam: Indexed code hasn't changed at all since 1.2

I can say with some authority that it has changed significantly.

I didn't suggest to remove the possibility to convert to indexed colors, I only
suggested to drop support from the core. And yes, as Adam pointed out already,
the code has been more or less completely redone since GIMP 1.2. Bolsh, what are
you talking?

Adam: Really? What's changed? 

Given that most of the work in 1.3 was done by Sven and mitch, and neither of
them are particularly interested in indexed mode, I had assumed that the various
bug fixes which were applied to both branches and some palette sorting features
and the like were all that were added.

So I am surprised to hear that it has been more or less completely redone. I
thought that it had just been refactored into GObjects.

Pedro says in Comment #24:

> If anyone else can figure out how to let gimp know what the
> corporate colors of an enterprise are, suggestons are welcome.

That's what a custom palette is for. When I do design work, I create a palette
for the customer with her colors in it. The palette is handy anyway since you'll
probably need those colors a lot.

The "keep predominant colors" option could probably be implemented by a special
plugin "create palette from predominant colors" - all sorts of fancy options
could go in there (including taking an existing palette as a starting point).

If I only had to create a palette from the 5-10 predominant colors (and not
all the shades and blends), the option could be left out.

For me, the "add colors as needed" option would suffice and make work a lot
easier.

Sven: If you take simple Logos and web stuff in general, indexed mode saves a 
lot of bandwidth! Storing everything as RGB-PNG makes it pretty big since
often JPEG is not an option (for example, smooth gradients suffer a lot) while 
an indexed picture would do well.

> Adam: Really? What's changed? 

Quantization and dithering moved to L*a*b* space, the box cut algo got another
overhaul, and various other stuff.

Sven: please avoid posting unrelated comments. It makes bug reports harder to
read and reduces the likelihood to get that bug fixed. If you want to have
indexed mode removed please open a separate bug report (maybe as an enhancement
request). This bug is about distortion of colors in the indexed conversion,
which would still be a problem even after removing indexed mode from the core
(as you pointed out there would still be a way to convert to indexed colors).

bolsh: there is a File in CVS thats called Changelog.pre-2-0, look for a commit
from Adam. I found one from 2002-02-10 that seems quite significant.

Can we get ontopic now again?  ;)

About Tino's comment #31:

I'm only saying that bug #66258 would be the right place for this kind of
solution, since according to the bug description and Yeti's comment #17 this bug
is about keeping the colors that are visually more apparent. It is already quite
confusing to have them as separate, so please don't mix them since that
increases the confusion even more.

I'm sure that Yeti won't agree to create a palette with the predominant colors
of the image he wants to convert. Me neither, for the record. Each image can
have different predominant colors and you can end up with mess of palettes if
you forget to delete them when done.

Please post further comments on the topic of using a palette as a method for
locking colors to bug #66258. Thanks.

The solution I see is quite straight forward:

Have an option right below the "Maximum number of colours [NNN]" control that is 
called something like "Keep the [NNN] most prominent colours".  It would range 
from 0 (which would be ideal for indexing photographic material) to the total 
number of colours in the index (which would simply drop the least prominent 
colours from the image and replace them with whatever the the closest remaining 
colour was).

To determine the most "prominent" colours, all that would need to be done is 
make a table of each individual colour in the image and how many pixels use it, 
sorted from most to least.

This would give the most flexibility with the least confusing controls.  I would 
think a good default for "Keep the [NNN] most prominent colours" would be half 
of the total colours in the index, rather than the current 0.

I like to use The GIMP for screenshots as I always have it open on my desktop, 
but this bug prevents me from saving 7 or 8bit PNGs -- it makes solid grey 
windows very noticeably green.  The only solutions I have come up with are to 
use 1:1 ratio JPEG images, which tend to lose very little of the pixel data, or 
to save the full 24bit PNG and then use ImageMagick to convert it to 8bit 
without loss of the image's significant colours.

G'day.

Your suggestions are reasonable, but they are addressing the easy part of the
problem.  The hard part is to modify the color-choosing algorithm so that it
finds colors to complement the preserved colors, rather than starting from
scratch.  (See comment #2 etc.)

*** Bug 331198 has been marked as a duplicate of this bug. ***

Here's how I see it.  There are 3 stages:

1.  All colors present in the image (or layers for animations) are put into a list of colors and how many pixels use that color.  The color list should be able to exceed 256 colors.
2.  The colors are then sorted from most common to least common.
3.  The rare colors, those beyond index FF (255), get averaged out using the color-averaging formula.  If color 255 was FF8000 and had 5 pixels of it and color 256, beyond the limit, was 4080FF and had 4 pixels of it the last color on the palette would be, mixed in a 5:4 ratio, AA8071.

For several colors, and many rare ones, a balancing system should be used.  That is, if color FD had 8, FE had 7, FF had 7, 100 had 6, 101 had 3, and 102 had 2, then color FD would an 8:2 blend of FD and 102, color FE would be a 7:3 blend of FE and 101, and color FF would be a 7:6 blend of FF and 100.  This is the best method I can come up with.

I agree with comment #36 the hard part is the dithering algorithm to find the remaining colours.  Anyway, seeing the suggestions I have to comment on the easy part...

Pixel counts are not crucial.  What makes a colour a candidate for exact preservation is not its pixel count but the fact it forms continuous areas.  High pixel count is just a common consequence.  If a colour is already scattered, further dithering can preserve the visual impression well (with a sufficient target palette), the problem occurs with large continuous areas.

For start, I suggest to use a simple measure of continuity instead of pixel counts -- for example based on the number of identical neighbours of each pixel.

-- GitLab Migration Automatic Message --

This bug has been migrated to GNOME's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/gimp/issues/13.