Map colors in image to closest member of a list of colors, in Python

Question

I have a list of 19 colors, which is a numpy array of size (19,3):

colors = np.array([[0, 0, 0], 
[0, 0, 255], 
[255, 0, 0], 
[150, 30, 150], 
[255, 65, 255], 
[150, 80, 0], 
[170, 120, 65], 
[125, 125, 125], 
[255, 255, 0], 
[0, 255, 255], 
[255, 150, 0], 
[255, 225, 120], 
[255, 125, 125], 
[200, 100, 100], 
[0, 255, 0], 
[0, 150, 80], 
[215, 175, 125], 
[220, 180, 210], 
[125, 125, 255]
])

Now I have an image (numpy array of size (1024,1024,3)), with colors that are somewhat close or equal to all of the colors defined above. However, my program requires that the image can only contain the colors above and not a closeby color, so I need to convert the color of each pixel in the array to the closest color of the 19 colors.

I saw a function to find the closest color from a set of colors that uses only Numpy (which works perfectly) here Python - Find the closest color to a color, from giving list of colors:

def closest_color(colors,color):
    colors = np.array(colors)
    color = np.array(color)
    distances = np.sqrt(np.sum((colors-color)**2,axis=1))
    index_of_smallest = np.where(distances==np.amin(distances))
    smallest_distance = colors[index_of_smallest]
return smallest_distance

With this function I can find the closest color to a single color from a predefined list, but in my problem I do not have a single color that I would like to change but a whole image (1024 x 1024 pixels of colors). What is the most efficient way to leverage this function (or using any better function) that uses numpy only to solve my problem. I would like to reduce the amount of for loops as much as possible, since I need process 30,000 images of size 1024 x 1024 in total.

Thanks!

Answer 1

We can use Cython-powered kd-tree for quick nearest-neighbor lookup and hence achieve our classification/bucketing -

from scipy.spatial import cKDTree

# Input image : img
out_img = colors[cKDTree(colors).query(img,k=1)[1]]

Answer 2

The question not only asks for finding the nearest neighbor - which the other answers provide - but how to efficiently apply the exchange over 30000 images.

Performance improvement:

Instead of computing the distance per pixel per image (30000*1024*1024 = 31457280000), compute a mapping once for each possible color onto your palette.

Then use that mapping to exchange the pixels.

import numpy as np
import itertools as it
import scipy.spatial.distance

palette  = np.array([[0, 0, 0], 
[0, 0, 255], 
[255, 0, 0], 
[150, 30, 150], 
[255, 65, 255], 
[150, 80, 0], 
[170, 120, 65], 
[125, 125, 125], 
[255, 255, 0], 
[0, 255, 255], 
[255, 150, 0], 
[255, 225, 120], 
[255, 125, 125], 
[200, 100, 100], 
[0, 255, 0], 
[0, 150, 80], 
[215, 175, 125], 
[220, 180, 210], 
[125, 125, 255]
])

valueRange = np.arange(0,256)
allColors = np.array(list(it.product(valueRange,valueRange,valueRange)))
mapping = scipy.spatial.distance.cdist(allColors, palette).argmin(1)

In addition I recommend the lecture of Creating fast RGB look up tables in Python