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 > [email protected] > http://mail.gnome.org/mailman/listinfo/gimp-developer-list
_______________________________________________ gimp-developer-list mailing list [email protected] http://mail.gnome.org/mailman/listinfo/gimp-developer-list
