Re: [Gimp-developer] the indexed mode implementation

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
> 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

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]