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

概述

这是解决问题的可能方法：

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

2）如果生成的调色板大于允许的最大颜色数，则通过从计算的调色板中删除彼此最相似的颜色，调色板将减少到允许的最大数量（我确实选择了最近的距离进行删除，因此生成的图像仍然具有高对比度）。

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

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

实现

下面是此方法的实现。

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

对于调色板缩减算法，可以在 3 种不同的约简策略之间进行选择：

1）：此算法通过在调色板中搜索距离最小的两种颜色，尝试尽可能忠于输入像素颜色。从这两种颜色中，它删除了输入映射中像素映射最少的颜色。ORIGINAL_COLORS

2）：工作原理类似于，不同之处在于，从两种颜色中，它删除了与调色板其余部分的平均距离最低的颜色。BETTER_CONTRASTORIGINAL_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这样的抖动算法可能会更好。在主页末尾的“待办事项列表”上，他们写道：

[待办事项：]将某些颜色固定到预定集的能力（由算法支持，但当前实现不支持）

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

Ximagic Quantizer是一个Photoshop插件，用于图像颜色量化（颜色减少）和抖动。提供：预定义的调色板量化

3）填充调色板的算法也许可以改进 - 例如，根据颜色的平均距离填充调色板（如在约简算法中）。但这应该根据最终使用的抖动算法进行测试。

编辑：我想我可能回答了一个稍微不同的问题。jarnbjo指出了我的解决方案可能存在问题，我意识到我误解了这个问题。不过，我在这里留下我的答案给后代。

我可能在Matlab中有一个解决方案。为了找到最接近的颜色，我在这里的评论中使用了Albert Renshaw给出的权重。我使用了HSV色彩空间，但代码的所有输入都是标准RGB。灰度图像被转换为3通道灰度图像。

为了选择要使用的最佳颜色，我用测试样品调色板播种了 kmeans，然后将质心重置为样品托盘中最接近的值。

function imo = recolor(im,new_colors,max_colors)

% Convert to HSV
im2 = rgb2hsv(im);
new_colors = rgb2hsv(new_colors);

% Get number of colors in palette
num_colors = uint8(size(new_colors,1));

% Reshape image so every row is a diferent pixel, and every column a channel
% this is necessary for kmeans in Matlab
im2 = reshape(im2, size(im,1)*size(im,2),size(im,3));

% Seed kmeans with sample pallet, drop empty clusters
[IDX, C] = kmeans(im2,max_colors,'emptyaction','drop');

% For each pixel, IDX tells which cluster in C it corresponds to
% C contains the centroids of each cluster


% Because centroids are adjusted from seeds, we need to select which original color
% in the palette it corresponds to. We cannot be sure that the centroids in C correspond
% to their seed values
% Note that Matlab starts indexing at 1 instead of 0
for i=1:size(C,1)
    H = C(i,1);
    S = C(i,2);
    V = C(i,3);
    bdel = 100;
    % Find which color in the new_colors palette is closest
    for j=1:size(new_colors,1)
        H2 = new_colors(j,1);
        S2 = new_colors(j,2);
        V2 = new_colors(j,3);
        dH = (H2-H)^2*0.475;
        dS = (S2-S)^2*0.2875;
        dV = (V2-V)^2*0.2375;
        del = sqrt(dH+dS+dV);
        if isnan(del)
            continue
        end
        % update if the new delta is lower than the best
        if del<bdel
            bdel = del;
            C(i,:) = new_colors(j,:);
        end
    end
end

% Update the colors, this is equal to the following
% for i=1:length(imo)
%    imo(i,:) = C(IDX(i),:) 
imo = C(IDX,:);

% put it back in its original shape
imo = reshape(imo, size(im));

imo = hsv2rgb(imo);

imshow(imo);

正如我所写的那样，它现在的问题是彩色图像非常慢（Lenna花了几分钟）。

这是否符合您正在寻找的思路？

示例。

如果您不理解所有 Matlab 符号，请告诉我。