Colorization and Palette Best-Fit Algorithms

Question

Been poking around google and haven't found any like what I'm after. so what is it I'm after? well two things:

• firstly I'm looking for an algorithm/pseudo-code/white-papers to determine a best-fit color for a give r,g,b tuple from and array of 256 RGB tuples.

• Secondly, I'm looking for an algorithm/pseudo-code/white-papers to recolor a 8bit palette image(using the above RGB palette) to either a given Hue/Saturation or by r,g,b channel modification. also would be nice if it was possible to add a fix for gamma and artifacting pixels in the colorization as well.

anyone got any hints/pointers/tips as to where I might find such a thing(I know they must exist, else a few of photoshops functions wouldn't)

UPDATE: here is a basic euclidean distance RGB to palette index finder:

uint_8 __stdcall GFXUTIL_GetNearestPaletteIndex(const uint_8* pPalette, size_t nSize, uint_8 nRed, uint_8 nGreen, uint_8 nBlue)
{
    if(pPalette == NULL)
        return 0;

    int nDistance = -1;
    size_t nIndex = 0, nFoundIndex = 0;
    while(nIndex < nSize)
    {
        int nDistRed = pPalette[0] - nRed;
        int nDistGreen = pPalette[1] - nGreen;
        int nDistBlue = pPalette[2] - nBlue;
        int nCurrentDistance = (nDistRed * nDistRed) + (nDistGreen * nDistGreen) + (nDistBlue * nDistBlue);
        if(nCurrentDistance < nDistance)
        {
            nFoundIndex = nIndex;
            nDistance = nCurrentDistance;
        }

        nIndex++;
        pPalette += sizeof(uint_32);
    }

    return nFoundIndex;
} 

Answer 1

See http://en.wikipedia.org/wiki/Color_difference for how to calculate distances between colors so that human eye sensitivity is taken into account.

Answer 2

If you want it faster than linear search, then check out VP-tree or KD-tree.

If you want it perceptually accurate, then do the search in Lab color space.