java - 使用M种预定义颜色中的N种进行颜色量化

Question

我在尝试量化和抖动RGB图像时遇到了一个有点奇怪的问题。理想情况下，我应该能够用Java实现合适的算法或使用Java库，但是引用其他语言的实现也可能会有所帮助。

提供以下内容作为输入:

image:24位RGB位图

palette:用其RGB值定义的颜色列表

max_cols:输出图像中使用的最大颜色数

重要的是，调色板的大小以及允许的最大颜色数不一定都是2的幂，并且可能大于255。

因此，目标是采用 image，从提供的 max_cols中选择多达 palette种颜色，并仅使用所选择的颜色输出图像，并使用某种误差扩散抖动进行渲染。使用哪种抖动算法并不重要，但是应该是误差扩散变体(例如Floyd-Steinberg)，而不是简单的半色调或有序抖动。

性能并不是特别重要，预期数据输入的大小相对较小。图片很少会大于500x500像素，提供的调色板可能包含3-400种颜色，并且颜色数量通常会限制为少于100种。也可以安全地假设调色板包含多种颜色，涵盖色调，饱和度和亮度的变化。

scolorq使用的调色板选择和抖动将是理想的选择，但是要使该算法从已经定义的调色板中选择颜色而不是任意颜色似乎并不容易。

更准确地说，我遇到的问题是从提供的调色板中选择合适的颜色。假设我使用scolorq创建具有N种颜色的调色板，然后用提供的调色板中最接近的颜色替换scolorq定义的颜色，然后将这些颜色与误差扩散的抖动结合使用。这将产生至少与输入图像相似的结果，但是由于所选颜色的色调无法预测，因此输出图像可能会获得强烈的不希望有的偏色。例如。当使用灰度输入图像和调色板时，只有很少的中性灰色调，但是有很大范围的棕色调(或更广泛地说，许多具有相同色调，低饱和度和亮度变化很大的颜色)，我的颜色选择算法似乎比中性灰色更喜欢这些颜色，因为棕色色调在数学上至少比灰色更接近所需颜色。即使我尝试将RGB值转换为HSB并在查找最接近的可用颜色时对H，S和B channel 使用不同的权重，仍然存在相同的问题。

有什么建议如何正确地实现这一点，或者甚至更好的是我可以用来执行任务的库吗？

自从Xabster询问以来，我也可以用这个练习来解释目标，尽管它与如何解决实际问题无关。输出图像的目标是绣花或挂毯图案。在最简单的情况下，输出图像中的每个像素对应于在某种载体织物上进行的针迹。调色板对应于可用的 yarn ，通常有数百种颜色。但是，出于实际原因，有必要限制实际工作中使用的颜色数量。 Gobelin刺绣的谷歌搜索将给出几个示例。

并弄清问题出在哪里...解决方案的确可以分为两个单独的步骤:

选择原始调色板的最佳子集

使用子集渲染输出图像

在这里，第一步是实际的问题。如果调色板选择正常工作，我可以简单地使用所选的颜色，例如Floyd-Steinberg抖动可产生合理的结果(实现起来相当琐碎)。

如果我正确理解scolorq的实现，则scolorq会结合这两个步骤，使用调色板选择中的抖动算法知识来创建更好的结果。当然，这将是首选的解决方案，但是scolorq中使用的算法的工作超出了我的数学知识。

Answer 1

概述

这是解决该问题的一种可能方法:

1)输入像素中的每种颜色都映射到输入调色板中最接近的颜色。

2)如果生成的调色板大于允许的最大颜色数量，则通过从计算的调色板中删除彼此最相似的颜色，调色板将减少到最大允许数量(我确实选择了最接近的距离移除，因此得到的图像对比度很高)。

3)如果生成的调色板小于允许的最大颜色数，则它将使用输入调色板其余颜色中最相似的颜色填充，直到达到允许的颜色数为止。希望这样做是为了使抖动算法可以在抖动期间利用这些颜色。注意尽管我没有看到填充或不填充Floyd-Steinberg算法的调色板之间没有太大区别...

4)作为最后一步，输入像素与计算的调色板抖动。

IMPLEMENTATION

以下是此方法的实现。

如果要运行源代码，则需要此类:ImageFrame.java。您可以将输入图像设置为唯一的程序参数，所有其他参数必须在main方法中设置。使用的Floyd-Steinberg算法来自Floyd-Steinberg dithering。

可以为调色板缩减算法选择3种不同的缩减策略:

1)ORIGINAL_COLORS:该算法通过在调色板中搜索距离最小的两种颜色，尝试尽可能地保持对输入像素的颜色真实。从这两种颜色中，它将删除到输入映射中与像素的映射最少的一种。

2)BETTER_CONTRAST:类似于ORIGINAL_COLORS，区别在于从两种颜色中删除与调色板其余部分的平均距离最低的一种。

3)AVERAGE_DISTANCE:此算法始终从池中删除平均距离最小的颜色。此设置可以特别提高灰度调色板所生成图像的质量。

这是完整的代码:

import java.awt.Color;
import java.awt.Image;
import java.awt.image.PixelGrabber;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class Quantize {

public static class RGBTriple {
    public final int[] channels;
    public RGBTriple() { channels = new int[3]; }

    public RGBTriple(int color) { 
        int r = (color >> 16) & 0xFF;
        int g = (color >> 8) & 0xFF;
        int b = (color >> 0) & 0xFF;
        channels = new int[]{(int)r, (int)g, (int)b};
    }
    public RGBTriple(int R, int G, int B)
    { channels = new int[]{(int)R, (int)G, (int)B}; }
}

/* The authors of this work have released all rights to it and placed it
in the public domain under the Creative Commons CC0 1.0 waiver
(http://creativecommons.org/publicdomain/zero/1.0/).

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Retrieved from: http://en.literateprograms.org/Floyd-Steinberg_dithering_(Java)?oldid=12476
 */
public static class FloydSteinbergDither
{
    private static int plus_truncate_uchar(int a, int b) {
        if ((a & 0xff) + b < 0)
            return 0;
        else if ((a & 0xff) + b > 255)
            return (int)255;
        else
            return (int)(a + b);
    }


    private static int findNearestColor(RGBTriple color, RGBTriple[] palette) {
        int minDistanceSquared = 255*255 + 255*255 + 255*255 + 1;
        int bestIndex = 0;
        for (int i = 0; i < palette.length; i++) {
            int Rdiff = (color.channels[0] & 0xff) - (palette[i].channels[0] & 0xff);
            int Gdiff = (color.channels[1] & 0xff) - (palette[i].channels[1] & 0xff);
            int Bdiff = (color.channels[2] & 0xff) - (palette[i].channels[2] & 0xff);
            int distanceSquared = Rdiff*Rdiff + Gdiff*Gdiff + Bdiff*Bdiff;
            if (distanceSquared < minDistanceSquared) {
                minDistanceSquared = distanceSquared;
                bestIndex = i;
            }
        }
        return bestIndex;
    }

    public static int[][] floydSteinbergDither(RGBTriple[][] image, RGBTriple[] palette)
    {
        int[][] result = new int[image.length][image[0].length];

        for (int y = 0; y < image.length; y++) {
            for (int x = 0; x < image[y].length; x++) {
                RGBTriple currentPixel = image[y][x];
                int index = findNearestColor(currentPixel, palette);
                result[y][x] = index;

                for (int i = 0; i < 3; i++)
                {
                    int error = (currentPixel.channels[i] & 0xff) - (palette[index].channels[i] & 0xff);
                    if (x + 1 < image[0].length) {
                        image[y+0][x+1].channels[i] =
                                plus_truncate_uchar(image[y+0][x+1].channels[i], (error*7) >> 4);
                    }
                    if (y + 1 < image.length) {
                        if (x - 1 > 0) {
                            image[y+1][x-1].channels[i] =
                                    plus_truncate_uchar(image[y+1][x-1].channels[i], (error*3) >> 4);
                        }
                        image[y+1][x+0].channels[i] =
                                plus_truncate_uchar(image[y+1][x+0].channels[i], (error*5) >> 4);
                        if (x + 1 < image[0].length) {
                            image[y+1][x+1].channels[i] =
                                    plus_truncate_uchar(image[y+1][x+1].channels[i], (error*1) >> 4);
                        }
                    }
                }
            }
        }
        return result;
    }

    public static void generateDither(int[] pixels, int[] p, int w, int h){
        RGBTriple[] palette = new RGBTriple[p.length];
        for (int i = 0; i < palette.length; i++) {
            int color = p[i];
            palette[i] = new RGBTriple(color);
        }
        RGBTriple[][] image = new RGBTriple[w][h];
        for (int x = w; x-- > 0; ) {
            for (int y = h; y-- > 0; ) {
                int index = y * w + x;
                int color = pixels[index];
                image[x][y] = new RGBTriple(color);
            }
        }

        int[][] result = floydSteinbergDither(image, palette);
        convert(result, pixels, p, w, h);

    }

    public static void convert(int[][] result, int[] pixels, int[] p, int w, int h){
        for (int x = w; x-- > 0; ) {
            for (int y = h; y-- > 0; ) {
                int index = y * w + x;
                int index2 = result[x][y];
                pixels[index] = p[index2];
            }
        }
    }
}

private static class PaletteColor{
    final int color;
    public PaletteColor(int color) {
        super();
        this.color = color;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + color;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        PaletteColor other = (PaletteColor) obj;
        if (color != other.color)
            return false;
        return true;
    }

    public List<Integer> indices = new ArrayList<>();
}


public static int[] getPixels(Image image) throws IOException {
    int w = image.getWidth(null);
    int h = image.getHeight(null);        
    int pix[] = new int[w * h];
    PixelGrabber grabber = new PixelGrabber(image, 0, 0, w, h, pix, 0, w);

    try {
        if (grabber.grabPixels() != true) {
            throw new IOException("Grabber returned false: " +
                    grabber.status());
        }
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    return pix;
}

/**
 * Returns the color distance between color1 and color2
 */
public static float getPixelDistance(PaletteColor color1, PaletteColor color2){
    int c1 = color1.color;
    int r1 = (c1 >> 16) & 0xFF;
    int g1 = (c1 >> 8) & 0xFF;
    int b1 = (c1 >> 0) & 0xFF;
    int c2 = color2.color;
    int r2 = (c2 >> 16) & 0xFF;
    int g2 = (c2 >> 8) & 0xFF;
    int b2 = (c2 >> 0) & 0xFF;
    return (float) getPixelDistance(r1, g1, b1, r2, g2, b2);
}

public static double getPixelDistance(int r1, int g1, int b1, int r2, int g2, int b2){
    return Math.sqrt(Math.pow(r2 - r1, 2) + Math.pow(g2 - g1, 2) + Math.pow(b2 - b1, 2));
}

/**
 * Fills the given fillColors palette with the nearest colors from the given colors palette until
 * it has the given max_cols size.
 */
public static void fillPalette(List<PaletteColor> fillColors, List<PaletteColor> colors, int max_cols){
    while (fillColors.size() < max_cols) {
        int index = -1;
        float minDistance = -1;
        for (int i = 0; i < fillColors.size(); i++) {
            PaletteColor color1 = colors.get(i);
            for (int j = 0; j < colors.size(); j++) {
                PaletteColor color2 = colors.get(j);
                if (color1 == color2) {
                    continue;
                }
                float distance = getPixelDistance(color1, color2);
                if (index == -1 || distance < minDistance) {
                    index = j;
                    minDistance = distance;
                }
            }
        }
        PaletteColor color = colors.get(index);
        fillColors.add(color);
    }
}

public static void reducePaletteByAverageDistance(List<PaletteColor> colors, int max_cols, ReductionStrategy reductionStrategy){
    while (colors.size() > max_cols) {
        int index = -1;
        float minDistance = -1;
        for (int i = 0; i < colors.size(); i++) {
            PaletteColor color1 = colors.get(i);
            float averageDistance = 0;
            int count = 0;
            for (int j = 0; j < colors.size(); j++) {
                PaletteColor color2 = colors.get(j);
                if (color1 == color2) {
                    continue;
                }
                averageDistance += getPixelDistance(color1, color2);
                count++;
            }
            averageDistance/=count;
            if (minDistance == -1 || averageDistance < minDistance) {
                minDistance = averageDistance;
                index = i;
            }
        }
        PaletteColor removed = colors.remove(index);
        // find the color with the least distance:
        PaletteColor best = null;
        minDistance = -1;
        for (int i = 0; i < colors.size(); i++) {
            PaletteColor c = colors.get(i);
            float distance = getPixelDistance(c, removed);
            if (best == null || distance < minDistance) {
                best = c;
                minDistance = distance;
            }
        }
        best.indices.addAll(removed.indices);

    }
}
/**
 * Reduces the given color palette until it has the given max_cols size.
 * The colors that are closest in distance to other colors in the palette
 * get removed first.
 */
public static void reducePalette(List<PaletteColor> colors, int max_cols, ReductionStrategy reductionStrategy){
    if (reductionStrategy == ReductionStrategy.AVERAGE_DISTANCE) {
        reducePaletteByAverageDistance(colors, max_cols, reductionStrategy);
        return;
    }
    while (colors.size() > max_cols) {
        int index1 = -1;
        int index2 = -1;
        float minDistance = -1;
        for (int i = 0; i < colors.size(); i++) {
            PaletteColor color1 = colors.get(i);
            for (int j = i+1; j < colors.size(); j++) {
                PaletteColor color2 = colors.get(j);
                if (color1 == color2) {
                    continue;
                }
                float distance = getPixelDistance(color1, color2);
                if (index1 == -1 || distance < minDistance) {
                    index1 = i;
                    index2 = j;
                    minDistance = distance;
                }
            }
        }
        PaletteColor color1 = colors.get(index1);
        PaletteColor color2 = colors.get(index2);

        switch (reductionStrategy) {
            case BETTER_CONTRAST:
                // remove the color with the lower average distance to the other palette colors
                int count = 0;
                float distance1 = 0;
                float distance2 = 0;
                for (PaletteColor c : colors) {
                    if (c != color1 && c != color2) {
                        count++;
                        distance1 += getPixelDistance(color1, c);
                        distance2 += getPixelDistance(color2, c);
                    }
                }
                if (count != 0 && distance1 != distance2) {
                    distance1 /= (float)count;
                    distance2 /= (float)count;
                    if (distance1 < distance2) {
                        // remove color 1;
                        colors.remove(index1);
                        color2.indices.addAll(color1.indices);
                    } else{
                        // remove color 2;
                        colors.remove(index2);
                        color1.indices.addAll(color2.indices);
                    }
                    break;
                }
                //$FALL-THROUGH$
            default:
                // remove the color with viewer mappings to the input pixels
                if (color1.indices.size() < color2.indices.size()) {
                    // remove color 1;
                    colors.remove(index1);
                    color2.indices.addAll(color1.indices);
                } else{
                    // remove color 2;
                    colors.remove(index2);
                    color1.indices.addAll(color2.indices);
                }
                break;
        }

    }
}

/**
 * Creates an initial color palette from the given pixels and the given palette by
 * selecting the colors with the nearest distance to the given pixels.
 * This method also stores the indices of the corresponding pixels inside the
 * returned PaletteColor instances.
 */
public static List<PaletteColor> createInitialPalette(int pixels[], int[] palette){
    Map<Integer, Integer> used = new HashMap<>();
    ArrayList<PaletteColor> result = new ArrayList<>();

    for (int i = 0, l = pixels.length; i < l; i++) {
        double bestDistance = Double.MAX_VALUE;
        int bestIndex = -1;

        int pixel = pixels[i];
        int r1 = (pixel >> 16) & 0xFF;
        int g1 = (pixel >> 8) & 0xFF;
        int b1 = (pixel >> 0) & 0xFF;
        for (int k = 0; k < palette.length; k++) {
            int pixel2 = palette[k];
            int r2 = (pixel2 >> 16) & 0xFF;
            int g2 = (pixel2 >> 8) & 0xFF;
            int b2 = (pixel2 >> 0) & 0xFF;
            double dist = getPixelDistance(r1, g1, b1, r2, g2, b2);
            if (dist < bestDistance) {
                bestDistance = dist;
                bestIndex = k;
            }
        }

        Integer index = used.get(bestIndex);
        PaletteColor c;
        if (index == null) {
            index = result.size();
            c = new PaletteColor(palette[bestIndex]);
            result.add(c);
            used.put(bestIndex, index);
        } else{
            c = result.get(index);
        }
        c.indices.add(i);
    }
    return result;
}

/**
 * Creates a simple random color palette
 */
public static int[] createRandomColorPalette(int num_colors){
    Random random = new Random(101);

    int count = 0;
    int[] result = new int[num_colors];
    float add = 360f / (float)num_colors;
    for(float i = 0; i < 360f && count < num_colors; i += add) {
        float hue = i;
        float saturation = 90 +random.nextFloat() * 10;
        float brightness = 50 + random.nextFloat() * 10;
        result[count++] = Color.HSBtoRGB(hue, saturation, brightness);
    }
    return result;
}

public static int[] createGrayScalePalette(int count){
    float[] grays = new float[count];
    float step = 1f/(float)count;
    grays[0] = 0;
    for (int i = 1; i < count-1; i++) {
        grays[i]=i*step;
    }
    grays[count-1]=1;
    return createGrayScalePalette(grays);
}

/**
 * Returns a grayscale palette based on the given shades of gray
 */
public static int[] createGrayScalePalette(float[] grays){
    int[] result = new int[grays.length];
    for (int i = 0; i < result.length; i++) {
        float f = grays[i];
        result[i] = Color.HSBtoRGB(0, 0, f);
    }
    return result;
}


private static int[] createResultingImage(int[] pixels,List<PaletteColor> paletteColors, boolean dither, int w, int h) {
    int[] palette = new int[paletteColors.size()];
    for (int i = 0; i < palette.length; i++) {
        palette[i] = paletteColors.get(i).color;
    }
    if (!dither) {
        for (PaletteColor c : paletteColors) {
            for (int i : c.indices) {
                pixels[i] = c.color;
            }
        }
    } else{
        FloydSteinbergDither.generateDither(pixels, palette, w, h);
    }
    return palette;
}

public static int[] quantize(int[] pixels, int widht, int heigth, int[] colorPalette, int max_cols, boolean dither, ReductionStrategy reductionStrategy) {

    // create the initial palette by finding the best match colors from the given color palette
    List<PaletteColor> paletteColors = createInitialPalette(pixels, colorPalette);

    // reduce the palette size to the given number of maximum colors
    reducePalette(paletteColors, max_cols, reductionStrategy);
    assert paletteColors.size() <= max_cols;

    if (paletteColors.size() < max_cols) {
        // fill the palette with the nearest remaining colors
        List<PaletteColor> remainingColors = new ArrayList<>();
        Set<PaletteColor> used = new HashSet<>(paletteColors);
        for (int i = 0; i < colorPalette.length; i++) {
            int color = colorPalette[i];
            PaletteColor c = new PaletteColor(color);
            if (!used.contains(c)) {
                remainingColors.add(c);
            }
        }
        fillPalette(paletteColors, remainingColors, max_cols);
    }
    assert paletteColors.size() == max_cols;

    // create the resulting image
    return createResultingImage(pixels,paletteColors, dither, widht, heigth);

}   

static enum ReductionStrategy{
    ORIGINAL_COLORS,
    BETTER_CONTRAST,
    AVERAGE_DISTANCE,
}

public static void main(String args[]) throws IOException {

    // input parameters
    String imageFileName = args[0];
    File file = new File(imageFileName);

    boolean dither = true;
    int colorPaletteSize = 80;
    int max_cols = 3;
    max_cols =  Math.min(max_cols, colorPaletteSize);

    // create some random color palette
    //  int[] colorPalette = createRandomColorPalette(colorPaletteSize);
    int[] colorPalette = createGrayScalePalette(20);

    ReductionStrategy reductionStrategy = ReductionStrategy.AVERAGE_DISTANCE;

    // show the original image inside a frame
    ImageFrame original = new ImageFrame();
    original.setImage(file);
    original.setTitle("Original Image");
    original.setLocation(0, 0);

    Image image = original.getImage();
    int width = image.getWidth(null);
    int heigth = image.getHeight(null);
    int pixels[] = getPixels(image);
    int[] palette = quantize(pixels, width, heigth, colorPalette, max_cols, dither, reductionStrategy);

    // show the reduced image in another frame
    ImageFrame reduced = new ImageFrame();
    reduced.setImage(width, heigth, pixels);
    reduced.setTitle("Quantized Image (" + palette.length + " colors, dither: " + dither + ")");
    reduced.setLocation(100, 100);

}
}

可能的改进

1)使用的Floyd-Steinberg算法目前仅适用于最大尺寸为 256种颜色的调色板。我猜这可能很容易解决，但是由于使用的FloydSteinbergDither类目前需要进行大量转换，因此从头开始实现该算法当然会更好，因此适合最终使用的颜色模型。

2)我相信使用其他抖动算法(例如 scolorq)可能会更好。他们在首页末尾的“待办事项 list ”上写道:

[TODO:] The ability to fix some colors to a predetermined set (supported by the algorithm but not the current implementation)

因此，对于该算法，似乎应该使用固定的调色板。 Photoshop/Gimp插件 Ximagic似乎使用scolorq实现了此功能。从他们的主页:

Ximagic Quantizer is a Photoshop plugin for image color quantization (color reduction) & dithering. Provides: Predefined palette quantization

3)可能会改善填充调色板的算法-例如通过根据调色板的平均距离为调色板填充颜色(例如在归约算法中)。但这应根据最终使用的抖动算法进行测试。