Find closest RGB color for every pixel in image

Question

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?

Are you sure `for i in range(len(im[x][y])):` is there? `i` is not used. — Divakar, Jan 31 '20 at 16:54
In your `getNearestColor` you sort again after each append. But you only have to sort one time, after you end that loop. Then again ... you don't have to maintain a list *at all* – you only want the closest color. — Jongware, Jan 31 '20 at 17:08
@hallowed your innermost for-loop doesn't do anything. It just repeats the exact same operation `len(im[x][y])` times. — Heike, Jan 31 '20 at 17:15
I actually only sort once. Formatted that wrong here. Want to you mean with "you don't need to maintain a list"? — itsame, Jan 31 '20 at 17:16
You don't need a list because you only want the nearest value. Initially, it's the distance to the first color. Then test the other colors, updating single variables `nearestColorDistance` and `nearestColorIndex` if closer. The result should be `nearestColorIndex` -- not `nearestColorDistance`, which you return now. — Jongware, Jan 31 '20 at 18:47

Jongware · Accepted Answer · 2020-01-31T20:37:41.810

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)

You are amazing! Thanks a lot! I'm obviously using the PIL implementation. But since I'm learning to program your answer was awesome to understand the concept behind it. But why is their method so much better/faster? — itsame, Jan 31 '20 at 20:55
@hallowed: large parts of PIL are [written in C](https://github.com/python-pillow/Pillow/tree/master/src) and are thus compiled to native executable code on your machine. Even a naive implementation in C will outperform anything in Python in this. (Disclaimer: you may notice I did not test with NumPy. It might do better than my own, but you have to read and write pixels using Python, so it's *likely* still not as fast as PIL.) — Jongware, Jan 31 '20 at 21:00
Could you explain what you did for the PIL implementation? What does this do `rgbValues = list(sum(rgbValues, ()))*12 rgbValues = rgbValues[:768]` the palette sequence must contain 768 integer values, this is somehow doing that (I would assume) but what is actually happening? — itsame, Jan 31 '20 at 21:35
Your 22 colors are not enough to fill an entire array of 3*256 values. You can't pad it with 0's because then the palette would contain a 23rd color. So this copies the list 12 times -> 264 RGB triples. That's too much so [a slice action](https://stackoverflow.com/questions/509211/understanding-slice-notation) cuts it down again. (Any further questions are best asked a-new, lest we'd be accused of "chat"...) — Jongware, Jan 31 '20 at 22:39

Find closest RGB color for every pixel in image

1 Answers1

Linked