Fast way to find the most similar color in an array

I have an image and a palette that I want to apply on that image, that is, change all colors of the image to match the closest they can find on the palette. While I have multiple ways to do it, I want to let the user choose if he wants the algorithm to be more precise, or faster.

The basic algorithm is this:

int pIndex = 0;
byte[] finalImage = new byte[image.width * image.height];
int s = colorTable.size;
IntBuffer pixels = image.getPixels();
while(pixels.hasRemaining()) {
    int pixel = pixels.get();
    int tableColor = colorTable.get(0).color;
    float minDst = someDistanceFunction(pixel, tableColor);
    int minIndex = 0;
    for(int i = 1; i < s; ++i) {
        tableColor = colorTable.get(i).color;
        float dst = someDistanceFunction(pixel, tableColor);
        if(dst < minDst) {
            minDst = dst;
            minIndex = i;
        }
    }
    finalImage[pIndex++] = (byte)minIndex;
}

If I do it like this, the finalImage array will have a collection of indices on the palette, which is exactly what I need.

The precise approach is kinda slow, but works awesomely, it will convert the integer RGB888 pixel to a float RGB, then to XYZ color space, then to LAB color space. Then again a quite expensive color distance function is used, but I don't care, it's supposed to be slow anyway, and the result is great.

Now to the part that I really care, is the fast way of doing it. My first attempt was to simply use the euclidean distance between the colors, and it turns out this works very good (very close result to the precise method), but the gain wasn't very big, around 20%, where I expected more.

This is how the algorithm went:

```
while(pixels.hasRemaining()) {
int pixel = pixels.get();
float r = ((pixel & 0xff000000) >>> 24) / 255.0f;
float g = ((pixel & 0x00ff0000) >>> 16) / 255.0f;
float b = ((pixel & 0x0000ff00) >>> 8) / 255.0f;
int tableColor = colorTable.get(0).color;
float r2 = ((tableColor & 0xff000000) >>> 24)

Some thoughts:

• If you can trade space for time, use a PixelColor object that keeps separate R, G, and B values instead of having to compute them every time.

• Even if pixels needs to remain int, there's no reason not to precompute and remember RGB for your palette, rather than recomputing for each pixel you're iterating over.

• Depending on how the flow of your application goes, it might make more sense to compute distances to the nearest palette point in the background whenever a palette color or point is added or removed.

• You don't need to special case i = 0. Start r2, g2, b2 at max int and index at -1. That'll make it a little easier to read.

• RGBDifferenceSquaredInteger should be rgbDifferenceSquaredInteger. Methods in Java always start with a lowercase letter.

A more OO approach might look like:

public final class Palette {

    public final List colors = ...;

    public int findClosestPaletteColorTo(final int color) {
        int closestColor = -1;
        int closestDistance = Integer.MAX_VALUE;
        for (final PaletteColor paletteColor : this.colors) {
            final int distance = paletteColor.distanceTo(color);
            if (distance >> 24);
            this.g = ((color & 0x00ff0000) >>> 16);
            this.b = ((color & 0x0000ff00) >>> 8);
            this.color = color;
        }

        public int distanceTo(final int color) {
            final int deltaR = this.r - ((color & 0xff000000) >>> 24);
            final int deltaG = this.g - ((color & 0x00ff0000) >>> 16);
            final int deltaB = this.b - ((color & 0x0000ff00) >>> 8);
            return (deltaR * deltaR) + (deltaG * deltaG) + (deltaB * deltaB);
        }

        public int asInt() {
            return this.color;
        }
    }
}

StackExchange Code Review Q#115046, answer score: 8