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