From: chrisg@cbmvax.commodore.com (Chris Green)
Newsgroups: comp.graphics
Subject: Re: color map. search
Date: 2 Sep 92 14:00:12 GMT
Reply-To: chrisg@cbmvax.commodore.com (Chris Green)
Organization: Commodore, West Chester, PA

In article <6yjnh0g.benoit@netcom.com> benoit@netcom.com (BENOIT SCHILLINGS) writes:
>Any idea someone about a smart way to search for the best
>match for a given logical color in a 256 color clut.
>Apple has a nice way AND a nice patent.
>
>benoit@netcom.com


    What I do is create a (for instance) 4096 entry table, each entry of
which contains a list of colors, indexed by the upper 4 bits of RGB, and an
error value. Since I am going to be using the table for each pixel, I can
afford a bit of setup time.

    There is a function MaxErr(r1,g1,b1,rmin,rmax,gmin,gmax,bmin,bmax)
which returns the maximum possible color error (by whatever metric)
between the given color and the max-min intervals. There is also a 
corresponding minimum error.

    init:

    	for(rgb=0..3)	(triply nested loop)
    	    find the "closest" color to r<<4,g<<4,b<<4, using
    	    linear search. Store this in list[r,g,b]. Store
    	    the maximum error possible with this color, also.

    	    while doing this loop, store the maximum of all the maxes.

    
    	now, the second pass:

    	    for each color in the colormap:

    	    	determine which colors it could possibly be a better fit
    	    	for than the one previously picked by using the minimum error
    	    	function. This will determine a 3d box of entries which
    	    	this color could potentially be added to. The global
    	    	maximum error above is used to determine this. Then:

    	    	for each entry in the 3d box:

    	    	maxerror=the maximum possible error from using this color
    	    	 for the given entry. i.e. MaxErr(testr,testg,testb,r<<4,r<<4+15,...)


    	    	minerror=the minimum possible error for using this color.

    	    	if (minerror < entry[rgb].maxerr) 
    	    	    add this color to the list.
    	    	    if maxerr < entry[rgb].maxerr, set entry[rgb].maxerr to maxerr.


    	When looking up colors, you quantize their upper bits and convert this
    to an index. If the given entry contains only one color, use it. Otherwise,
    search this (small) list of colors for the closest. In the (frequent) case
    of only one color in the list, this can happen in only 10 or so instructions.


    If N is the number of colormap entries, and B is the number of bits of 
    precision in the entry table, then the first pass takes N*2^(3*B) 
    operations. The second pass is of the same order as the first, but
    with a smaller coefficient typically.

    The Min and Max color error functions are trivial to implement with any 
    color error function which is of the form f1(delta_r)+f2(delta_g)+
    f3(delta_b), where f1,f2,f3 are monotonically increasing functions.
    More complex functions are a little harder.

    Insertions into the color table can be handled simply by running the
    2nd pass again for that color. Deletions require partially re-running the
    1st and 2nd passes for all entries which contain the deleted color.

    The number of bits to quantize on can be tuned to trade-off search speed
    against pre-processing/insertion/deletion speed.
-- 
*-------------------------------------------*---------------------------*
|Chris Green - Graphics Software Engineer   - chrisg@commodore.COM      f
|                  Commodore-Amiga          - uunet!cbmvax!chrisg       n
|My opinions are my own, and do not         - icantforgettheimpression  o
|necessarily represent those of my employer.- youmadeyouleftaholeinthe  r
|"A screaming comes across the sky..."      - backofmyhead              d
*-------------------------------------------*---------------------------*
Newsgroups: comp.graphics