How to reduce image palette to specific colors?

Question

I am playing with a program in Python to create cross stitch schemes and need to reduce colors in an image to specific floss colors like this. Not necessary to use all the colors from the floss palette. On Python or Pseudocode.

Example

Custom palette (in PILL/Pillow for example) is not situable. There 256 colors max, but floss palette has around 450 colors and I plan to use multiple color charts from different manufacturers.

Dithering also not situable in cross-stitching.

I think this could be something like:

result = []
for pixel_color in image:
    nearest = None
    for floss_color in floss_palette:
        distance = delta_e_cie2000(pixel_color, floss_color)
        if distance < nearest:
            nearest = floss_color
    result.append(nearest)

May be there is a faster algorithm? (image_width * image_heigh * colors in palette = 112M delta_e calculations and comparisons on average 500x500px image. It's a lot.)

Dictonary for already calculated delta_e? Another algorithm/aproach/optimization?

Rehabilitate

memoize - you don't need to retest colors that you've already done – Popsicle

Answer 1

Here is an example of memoize. I've also used the builtin min

def nearest(pixel_color, mem={}):
    if pixel_color in mem:
        return mem[pixel_color]
    n = min(floss_palette, key=lambda fc:delta_e_cie2000(pixel_color, fc))
    mem[pixel_color] = n
    return mem[pixel_color]

result = [nearest(pixel_color) for pixel_color in image]

Keppel

Looks nice. And then I can do PIL.Image.putdata(result)? Does it make sense 1) available_pixel_color = PIL.Image.getcolors, 2) Pass available_pixel_color to nearest to make dictionary, 3) apply this dictionary to pixel_color and get final list? – Rehabilitate

You can do result = PIL.Image.eval(image, nearest) to apply the reduction to all pixels. – Valueless