java - 어레이에서 가장 유사한 색상을 찾는 빠른 방법

이미지에 적용 할 이미지와 팔레트가 있습니다. 즉, 팔레트에서 찾을 수있는 가장 가까운 이미지와 일치하도록 이미지의 모든 색상을 변경하십시오. 여러 가지 방법이 있지만 사용자가 알고리즘을 더 정확하고 빠르게 원하는지 선택할 수 있도록하고 싶습니다.

기본 알고리즘은 다음과 같습니다 :

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

이렇게하면 finalImage  array에는 팔레트에 인덱스 모음이 있으며 정확히 필요한 것입니다.

정확한 접근 방식은 다소 느리지 만 훌륭하게 작동합니다. 정수 RGB888 픽셀을 부동 RGB로 변환 한 다음 XYZ 색상 공간, LAB 색상 공간으로 변환합니다. 그런 다음 조용한 값 비싼 색상 거리 기능 이 사용되지만 상관 없습니다. 어쨌든 속도가 느려 야합니다. 결과가 훌륭합니다.

이제 내가 정말로 신경 쓰는 부분은 바로하는 빠른 방법입니다. 첫 번째 시도는 단순히 색상 사이의 유클리드 거리를 사용하는 것이었고, 이것이 매우 잘 작동하는 것으로 나타났습니다 (정확한 방법에 매우 근접한 결과). 그러나 더 많은 것을 기대하는 곳에서는 이득이 약 20 % 정도로 크지 않았습니다.

이것은 알고리즘의 진행 방식입니다 :

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

실제 질문은 여기서 시작합니다

유클리드 거리에서 제곱근을 취하지 않기 때문에 실제로 부동 소수점 수학이 필요하지 않다는 생각을하게되므로 부동 소수점으로 변환하는 부분을 잘라 내고 계산합니다. 정수 수학에서의 거리 :

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

저는 원래의 정확한 LAB 알고리즘보다 약 20 배 빠른 성능을 발견했습니다. 그래서 나는 그것을 계속 땜질했다. 나는 이것이 변수를 오버플로 할까봐 두려웠지만 수학을 만들었고 그렇게하지 않을 것입니다 : 색상 범위는 0-255입니다. 단일 축의 최대 거리는 255 - 0 = 255 이므로 . 그것이 제곱 될 것이기 때문에, 255² = 65025 . 그리고 나는 3 축을 합쳐야하지만, 65025*3 = 195075  정수보다 용량이 작으므로 깨지지 않습니다.

코드가 더 빠르며 국경에 맞지 않는다는 것이 증명되었으므로 지금은 실제로 만족하지만정확성을 잃지 않으면 서 더 빠르게 만들 수 있습니까?