RSS/Atom feed Twitter
Site is read-only, email is disabled

Floyd-Steinberg/GIF color optimization

This discussion is connected to the gimp-developer-list.gnome.org mailing list which is provided by the GIMP developers and not related to gimpusers.com.

This is a read-only list on gimpusers.com so this discussion thread is read-only, too.

6 of 6 messages available
Toggle history

Please log in to manage your subscriptions.

Floyd-Steinberg/GIF color optimization Robert Hanson 21 Oct 15:04
  Floyd-Steinberg/GIF color optimization Mukund Sivaraman 21 Oct 15:47
   Floyd-Steinberg/GIF color optimization Robert Hanson 21 Oct 21:34
    Floyd-Steinberg/GIF color optimization Robert Hanson 10 Nov 03:20
     Floyd-Steinberg/GIF color optimization Robert Hanson 11 Nov 01:37
  Floyd-Steinberg/GIF color optimization Jernej Simončič 21 Oct 15:49
Robert Hanson
2014-10-21 15:04:14 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization

My name is Bob Hanson; I'm the principal developer of Jmol.

Jmol can export images in a variety of ways including GIF and animated GIF. But of course GIF only allows 256 colors, and I used to think that was the end of that. Forget that. But then one of our users pointed me to how well GIMP creates GIF images using the Floyd-Steinberg dithering algorithm, so I decided to give that a try. And I was delighted with the results. (Had some fun just playing with that -- see my 216-color solution at http://chemapps.stolaf.edu/jmol/test/dither.htm . The solution was to partition red, green, and blue channels into a 6 x 6 x 6 color space, allowing 216 colors in total. Not perfect, but amazingly good, I think.

The problem comes when I have a small molecule with not too many colors. If I go just over 256, then the FS algorithm cuts this down to something like 64 colors. I'm wondering if I could get some advise as to how to optimize a set of colors down to 255 colors without undershooting in such a dramatic way while still using FS.

Bob Hanson

Robert M. Hanson
Larson-Anderson Professor of Chemistry
Chair, Department of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr


If nature does not answer first what we want,
it is better to take what answer we get.

-- Josiah Willard Gibbs, Lecture XXX, Monday, February 5, 1900
Mukund Sivaraman
2014-10-21 15:47:32 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization

Hi Robert

On Tue, Oct 21, 2014 at 10:04:14AM -0500, Robert Hanson wrote:

http://chemapps.stolaf.edu/jmol/test/dither.htm . The solution was to

This page seems to use JavaScript and WebGL, and so I'm not able to view it. It would have been better if you had sent a link to static images of the source and result.

partition red, green, and blue channels into a 6 x 6 x 6 color space, allowing 216 colors in total. Not perfect, but amazingly good, I think.

So you are doing FS dithering with a fixed uniform palette?

The problem comes when I have a small molecule with not too many colors. If I go just over 256, then the FS algorithm cuts this down to something like 64 colors. I'm wondering if I could get some advise as to how to optimize a set of colors down to 255 colors without undershooting in such a dramatic way while still using FS.

You are looking for color quantization methods. You can find description of an octree method in Graphics Gems I. GIMP uses median cut.

See https://www.cs.cmu.edu/~ph/ciq_thesis for Heckbert's thesis on median cut.

Mukund

Jernej Simončič
2014-10-21 15:49:26 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization

On Tuesday, October 21, 2014, 17:04:14, Robert Hanson wrote:

The problem comes when I have a small molecule with not too many colors. If I go just over 256, then the FS algorithm cuts this down to something like 64 colors. I'm wondering if I could get some advise as to how to optimize a set of colors down to 255 colors without undershooting in such a dramatic way while still using FS.

In my opinion, the colour reduction algorithm in GIMP 1.2 produces better results than the algorithm in GIMP 2.x.

< Jernej Simoni ><><><><>< http://eternallybored.org/ >

Actually, it only SEEMS as though you mustn't be deceived by appearances.
       -- The Obvious Law
Robert Hanson
2014-10-21 21:34:44 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization

Thank you, Mukund, ...

On Tue, Oct 21, 2014 at 10:47 AM, Mukund Sivaraman wrote:

Hi Robert

On Tue, Oct 21, 2014 at 10:04:14AM -0500, Robert Hanson wrote:

http://chemapps.stolaf.edu/jmol/test/dither.htm . The solution was to

This page seems to use JavaScript and WebGL, and so I'm not able to view it. It would have been better if you had sent a link to static images of the source and result.

It's not WebGL -- just HTML5. But that is a fine idea: http://chemapps.stolaf.edu/jmol/test/dither2.htm

partition red, green, and blue channels into a 6 x 6 x 6 color space, allowing 216 colors in total. Not perfect, but amazingly good, I think.

So you are doing FS dithering with a fixed uniform palette?

That sounds right. I'm not familiar with the lingo here. Equal partitions along R G B coordinates.

The problem comes when I have a small molecule with not too many colors.

If

I go just over 256, then the FS algorithm cuts this down to something

like

64 colors. I'm wondering if I could get some advise as to how to

optimize a

set of colors down to 255 colors without undershooting in such a dramatic way while still using FS.

You are looking for color quantization methods. You can find description of an octree method in Graphics Gems I. GIMP uses median cut.

See https://www.cs.cmu.edu/~ph/ciq_thesis for Heckbert's thesis on median cut.

That's helpful. So we have n colors, each with p_i pixels. This median cut idea just
considers the n colors, not p_i, correct? (Ignores frequency?)

How is this then also implemented with Floyd-Steinberg dithering? Is the idea that
the averages of the median cut boxes form our fixed points for the dithering? That
a nearest-point calculation is done to generate the error function?

Can you point me to the place in the GIMP code this is accomplished?

Bob

Robert M. Hanson
Larson-Anderson Professor of Chemistry
Chair, Department of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr


If nature does not answer first what we want,
it is better to take what answer we get.

-- Josiah Willard Gibbs, Lecture XXX, Monday, February 5, 1900
Robert Hanson
2014-11-10 03:20:15 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization

Just a final word of thanks for the tips and suggestions relating to color quantization. Today I successfully implemented in Jmol and JSmol Floyd-Steinberg dithering and color quantization.* The implementation is quite different from GIMP's in the end, but the results are nearly identical. I'm sure GIMP is faster; I didn't aim for speed optimization, just acceptable results.

Many thanks.

Bob Hanson

* As far as I can see, at least in GIMP 2.8.0-RC1 app/core/imageconvert.c, the code for median cut is commented out, and what GIMP actually uses is just the average of highest and lowest values in a box, not the median. Unless I read that wrong, which is quite possible.... ​

Robert Hanson
2014-11-11 01:37:02 UTC (over 9 years ago)

Floyd-Steinberg/GIF color optimization