[FIXED] Find closest RGB color for every pixel in image

Issue

I'm using NumPy to do some image processing. I load an image into an array and get the "nearest" color for each pixel, as follows:

# rgbValues is a global list with 22 RGB values

def getNearestColor(rgb):
    a = []
    for i in range(len(rgbValues)):
        d = ((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2
        a.append(d)
    list.sort(a)
    return a[0]

im = np.asarray(Image.open('image.jpg'))

for x in range(len(im)):
    for y in range(len(im[x])):
        for _ in range(len(im[x][y])):
            out[x][y] = getNearestColor(im[x][y])

How can I get the actual RGB values in out, rather than the distances? How can I improve the performance of the code?

Solution

Your (corrected) function is:

def findNearest(rgb):
    a = []
    for i in range(len(rgbValues)):
        d = ((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2
        a.append([d,i])
    list.sort(a)
    return rgbValues[a[0][1]]

It returns the correct rgbValues; this is now possible because its index get stored in a as well. This – in an admittedly roughly timed framework – processes some 27,085 pixels per second.

A straightforward implementation, adjusted to remember only the nearest index:

def findNearest(rgb):
    dist = ((rgbValues[0][0]-rgb[0])*0.3)**2 + ((rgbValues[0][1]-rgb[1])*0.59)**2 + ((rgbValues[0][2]-rgb[2])*0.11)**2
    index = 0
    for i in range(1,len(rgbValues)):
        d = ((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2
        if d < dist:
            dist = d
            index = i
    return rgbValues[index]

already performs much better: 37,175 pixels per second, a speed improvement of 37%. Can we do better with a more Pythonic approach?

def findNearest(rgb):
    dist = [(((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2,i) for i in range(22)]
    return rgbValues[min(dist)[1]]

Nope. With the same image and the same timing mechanism it goes down to 33,417 pixels/sec.

---

Complete test program, using a random image from an earlier question (it uses PIL to load, access pixels, and display the image, but that is not relevant for the distance calculations):

import random
from PIL import Image
from time import time

def findNearest_org(rgb):
    a = []
    for i in range(len(rgbValues)):
        d = ((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2
        a.append([d,i])
    list.sort(a)
    return rgbValues[a[0][1]]

def findNearest_raw(rgb):
    dist = ((rgbValues[0][0]-rgb[0])*0.3)**2 + ((rgbValues[0][1]-rgb[1])*0.59)**2 + ((rgbValues[0][2]-rgb[2])*0.11)**2
    index = 0
    for i in range(1,len(rgbValues)):
        d = ((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2
        if d < dist:
            dist = d
            index = i
    return rgbValues[index]

def findNearest_list(rgb):
    dist = [(((rgbValues[i][0]-rgb[0])*0.3)**2 + ((rgbValues[i][1]-rgb[1])*0.59)**2 + ((rgbValues[i][2]-rgb[2])*0.11)**2,i) for i in range(22)]
    return rgbValues[min(dist)[1]]

image = Image.open('output-2.png')
pixels = image.load()
width, height = image.size

rgbValues = [tuple(random.randrange(0,256) for _ in range(3)) for _ in range(22)]

start = time()
for y in range(height):
    for x in range(width):
        # fetch the rgb value
        color = pixels[x,y]
        # replace with nearest
        pixels[x,y] = findNearest_list (color)
print ('pixels/sec:', (width*height)/(time()-start))

image.show()

and test images before and after:

If you are only interested in results, use whatever native method your image library allows. This short piece using PIL's own quantize

rgbValues = list(sum(rgbValues, ()))*12
rgbValues = rgbValues[:768]
palimage = Image.new('P', (width, height))
palimage.putpalette(rgbValues)
newimage = image.quantize(palette=palimage)

outsources the calculations to native code, and the results are quite staggeringly better: 18,443,414 pixels/sec – a whopping 500 times faster than my native (/naïve) implementation.
(Hyper-fancy tuple-to-list comes from https://stackoverflow.com/a/3205524)

Answered By - Jongware