Fastest way to find difference between image pixel and palette colour in Python

Question

I am working on some code for converting an image to the palette of the NES. My current code is somewhat successful, but very very slow.

I am doing it by using Pythagoras' theorem. I'm using the RGB colour values as coordinates in 3D space and doing it that way. The colour in the palette with the smallest distance from the pixel's RGB is the colour that gets used.

class image_filter():
    def load(self,path):
        self.i = Image.open(path)
        self.i = self.i.convert("RGB")
        self.pix = self.i.load()

    def colour_filter(self,colours=NES):
        start = time.time()
        for y in range(self.i.size[1]):
            for x in range(self.i.size[0]):
                pixel = list(self.pix[x,y])
                distances = []
                for colour in colours:
                    distance = ((colour[0]-pixel[0])**2)+((colour[1]-pixel[1])**2)+((colour[2]-pixel[2])**2)
                    distances.append(distance)
                pixel = colours[distances.index(sorted(distances,key=lambda x:x)[0])]
                self.pix[x,y] = tuple(pixel)
        print "Took "+str(time.time()-start)+" seconds."

f = image_filter()
f.load("C:\\path\\to\\image.png")
f.colour_filter()
f.i.save("C:\\path\\to\\new\\image.png")

Using the list:

NES = [(124,124,124),(0,0,252),
           (0,0,188),(68,40,188),
           (148,0,132),(168,0,32),
           (168,16,0),(136,20,0),
           (80,48,0),(0,120,0),
           (0,104,0),(0,88,0),
           (0,64,88),(0,0,0),
           (188,188,188),(0,120,248),
           (0,88,248),(104,68,252),
           (216,0,204),(228,0,88),
           (248,56,0),(228,92,16),
           (172,124,0),(0,184,0),
           (0,168,0),(0,168,68),
           (0,136,136),(248,248,248),
           (60,188,252),(104,136,252),
           (152,120,248),
           (248,120,248),(248,88,152),
           (248,120,88),(252,160,68),
           (184,248,24),(88,216,84),
           (88,248,152),(0,232,216),
           (120,120,120),(252,252,252),(164,228,252),
           (184,184,248),(216,184,248),
           (248,184,248),(248,164,192),
           (240,208,176),(252,224,168),
           (248,216,120),(216,248,120),
           (184,248,184),(184,248,216),
           (0,252,252),(216,216,216)]

This produces the following Input:

and Output:

This takes between 14 and 20 seconds, which is much too long for its intended application. Does anyone know of any ways to greatly speed this up?

As an idea, I was thinking it may be possible to use numpy arrays for this; however I am not at all familiar enough with numpy arrays to be able to pull it off.

If possible, I would also like to try avoiding using scipy -- I know that, at least under Windows, it can be a pain to install and would prefer to steer clear.

Answer 1

Approach #1 : We could use Scipy's cdist to get the euclidean distances and then look for the min distance arg and thus select the appropriate colour.

Thus, with NumPy arrays as the inputs, we would have an implementation like so -

from scipy.spatial.distance import cdist

out = colours[cdist(pix.reshape(-1,3),colours).argmin(1)].reshape(pix.shape)

---

Approach #2 : Here's another approach with broadcasting and np.einsum -

subs = pix - colours[:,None,None]
out = colours[np.einsum('ijkl,ijkl->ijk',subs,subs).argmin(0)]

---

Interfacing between PIL/lists and NumPy arrays

To accept images read through PIL, use :

pix = np.asarray(Image.open('input_filename'))

To Use colours as array :

colours = np.asarray(NES)

# .... Use one of the listed approaches and get out as output array

To output the image :

i = Image.fromarray(out.astype('uint8'),'RGB')
i.save("output_filename")

Sample input, output using given colour palette NES -