Hi,all.
I'm curious about how the indexed mode in gimp is implemented. Because I implemented a function which change a RGB colorspace image to indexed color image before, but my implementation is extremely slow. The algorithm is trivial, the runtime is about O(n^k), where n is number of pixels, k is the size of index. However, I tried indexed mode in GIMP on same image on same computer, it's really faster than my implementation. Could anyone give me some information about the indexed mode in GIMP? Thanks!

Best Regards
--ashi

Hi Ashi

On Sun, Apr 08, 2012 at 10:18:48PM +0800, 阿四 wrote:

Hi,all.
I'm curious about how the indexed mode in gimp is implemented. Because I implemented a function which change a RGB colorspace image to indexed

color

image before, but my implementation is extremely slow. The algorithm is trivial, the runtime is about O(n^k), where n is number of pixels, k is

the

size of index. However, I tried indexed mode in GIMP on same image on

same

computer, it's really faster than my implementation. Could anyone give me some information about the indexed mode in GIMP?

See this article (and the linked articles from there). Floyd Steinberg is very simple to implement and has a linear runtime:

http://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering

Mukund,thanks for your reply. However, dithering is not I want. I just want to know the pure index color.
Best regards
--ashi

Kind regards,

Mukund

Hi, Bill, thanks!!
I take a quick look at the comments, find it probably is what I want. I'll take a close look at this and related code!

Best regards --ashi

Dithering is not really where the problem lies, it's in finding a good colormap. Gimp's algorithm was developed a long time ago, by Adam Moss, who put a great deal of effort into it. The code can be found in app/core/gimpimage-convert.c in the Gimp source. The theory behind it is explained in a long comment way down in the source file, which I extract and append here:

/*
* These routines are concerned with the time-critical task of mapping

input

* colors to the nearest color in the selected colormap. *
* We re-use the histogram space as an "inverse color map", essentially a * cache for the results of nearest-color searches. All colors within a * histogram cell will be mapped to the same colormap entry, namely the

one

* closest to the cell's center. This may not be quite the closest entry

to

* the actual input color, but it's almost as good. A zero in the cache * indicates we haven't found the nearest color for that cell yet; the

array

* is cleared to zeroes before starting the mapping pass. When we find

the

* nearest color for a cell, its colormap index plus one is recorded in

the

* cache for future use. The pass2 scanning routines call

fill_inverse_cmap

* when they need to use an unfilled entry in the cache. *
* Our method of efficiently finding nearest colors is based on the

"locally

* sorted search" idea described by Heckbert and on the incremental

distance

* calculation described by Spencer W. Thomas in chapter III.1 of Graphics * Gems II (James Arvo, ed. Academic Press, 1991). Thomas points out

that

* the distances from a given colormap entry to each cell of the

histogram can

* be computed quickly using an incremental method: the differences

between

* distances to adjacent cells themselves differ by a constant. This

allows a

* fairly fast implementation of the "brute force" approach of computing

the

* distance from every colormap entry to every histogram cell.

Unfortunately,

* it needs a work array to hold the best-distance-so-far for each

histogram

* cell (because the inner loop has to be over cells, not colormap

entries).

* The work array elements have to be ints, so the work array would need * 256Kb at our recommended precision. This is not feasible in DOS

machines.

*
* To get around these problems, we apply Thomas' method to compute the * nearest colors for only the cells within a small subbox of the

histogram.

* The work array need be only as big as the subbox, so the memory usage * problem is solved. Furthermore, we need not fill subboxes that are

never

* referenced in pass2; many images use only part of the color gamut, so a * fair amount of work is saved. An additional advantage of this * approach is that we can apply Heckbert's locality criterion to quickly * eliminate colormap entries that are far away from the subbox; typically * three-fourths of the colormap entries are rejected by Heckbert's

criterion,

* and we need not compute their distances to individual cells in the

subbox.

* The speed of this approach is heavily influenced by the subbox size:

too

* small means too much overhead, too big loses because Heckbert's

criterion

* can't eliminate as many colormap entries. Empirically the best subbox * size seems to be about 1/512th of the histogram (1/8th in each

direction).

*
* Thomas' article also describes a refined method which is asymptotically * faster than the brute-force method, but it is also far more complex and * cannot efficiently be applied to small subboxes. It is therefore not * useful for programs intended to be portable to DOS machines. On

machines

* with plenty of memory, filling the whole histogram in one shot with

Thomas'

* refined method might be faster than the present code --- but then

again,

* it might not be any faster, and it's certainly more complicated. */

There probably is nobody in the universe except Adam who fully understands that, and Adam has not been an active developer for many years.

-- Bill
_______________________________________________ gimp-developer-list mailing list
gimp-developer-list@gnome.org
http://mail.gnome.org/mailman/listinfo/gimp-developer-list