Fast way to find the most similar color in an array

Question

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) / 255.0f;
    float g2 = ((tableColor & 0x00ff0000) >>> 16) / 255.0f;
    float b2 = ((tableColor & 0x0000ff00) >>> 8) / 255.0f;
    float minDst = Util.RGBDifferenceSquared(r, g, b, r2, g2, b2);
    int minIndex = 0;
    for(int i = 1; i < s; ++i) {
        tableColor = colorTable.get(i).color;
        r2 = ((tableColor & 0xff000000) >>> 24);
        g2 = ((tableColor & 0x00ff0000) >>> 16);
        b2 = ((tableColor & 0x0000ff00) >>> 8);
        float dst = Util.RGBDifferenceSquared(r, g, b, r2, g2, b2);
        if(dst < minDst) {
            minDst = dst;
            minIndex = i;
        }
    }
    finalImage[pIndex++] = (byte)minIndex;
}
float RGBDifferenceSquared(float r, float g, float b, float r2, float g2, float b2) {
    float deltaR = r1-r2;
    float deltaG = g1-g2;
    float deltaB = b1-b2;
    return deltaR*deltaR + deltaG*deltaG + deltaB*deltaB;
}

The real question begins here

Since I'm not taking the square root on the euclidean distance, I come up with the idea that I really don't need floating point math, so I cut up the part where I convert them to floats, and am calculating the distance in integer math:

while(pixels.hasRemaining()) {
    int pixel = pixels.get();
    int r = ((pixel & 0xff000000) >>> 24);
    int g = ((pixel & 0x00ff0000) >>> 16);
    int b = ((pixel & 0x0000ff00) >>> 8);
    int tableColor = colorTable.get(0).color;
    int r2 = ((tableColor & 0xff000000) >>> 24);
    int g2 = ((tableColor & 0x00ff0000) >>> 16);
    int b2 = ((tableColor & 0x0000ff00) >>> 8);
    float minDst = Util.RGBDifferenceSquaredInteger(r, g, b, r2, g2, b2);
    int minIndex = 0;
    for(int i = 1; i < s; ++i) {
        tableColor = colorTable.get(i).color;
        r2 = ((tableColor & 0xff000000) >>> 24);
        g2 = ((tableColor & 0x00ff0000) >>> 16);
        b2 = ((tableColor & 0x0000ff00) >>> 8);
        float dst = Util.RGBDifferenceSquaredInteger(r, g, b, r2, g2, b2);
        if(dst < minDst) {
            minDst = dst;
            minIndex = i;
        }
    }
    finalImage[pIndex++] = (byte)minIndex;
}
public static int RGBDifferenceSquaredInteger(int r1, int g1, int b1, int r2, int g2, int b2) {
    int deltaR = r1-r2;
    int deltaG = g1-g2;
    int deltaB = b1-b2;
    return deltaR*deltaR + deltaG*deltaG + deltaB*deltaB;
}

I found out the performance to be about 20x faster than the original precise LAB algorithm. So I continued to tinker with it. I was afraid that this might overflow the variables, but I made the math and it won't: A color ranges from 0-255. Since the maximum distance in a single axis will be 255 - 0 = 255. Since it's going to be squared, 255² = 65025. And while I have to sum the 3 axis, 65025*3 = 195075 and that's way below the capacity of a integer, so it won't break;

As I proved that the code is faster and won't break in any border-case, I'm actually happy with it right now, but can it be made even faster without losing much more precision?

Answer 1

Some thoughts:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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<PaletteColor> 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 < closestDistance) {
                closestDistance = distance;
                closestColor = paletteColor.asInt();
            }
        }
        return closestColor;
    }

    private static final class PaletteColor {
        private final int r;
        private final int g;
        private final int b;
        private final int color;

        public PaletteColor(final int color) {
            this.r = ((color & 0xff000000) >>> 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;
        }
    }
}