PIL posterize- fix green pixels

Question

I decided to write my own posterize function in PIL instead of using the provided one so that I could understand it more.

Problem

Sometimes, unexpected green pixels show up when using my posterize function that don't when using the built-in posterize function.

Example

The first picture is the input and output of my posterize function to 4 levels. The second one is the input and output of the built-in posterize function.

Closeup

How mine works

My posterize function works by figuring out thresholds, using bisect_left to put each element of a RGB tuple into a slot, and reassigning it the threshold value, like so.

def posterize(im, levels):

    #Figure out thresholds for the pixel colors
    increment = 255//levels
    thresholds = range(1, 256, increment)
    
    im = copy.copy(im)
    img = im.load()
    #Iterate through the image
    for y in range(im.size[1]):
        for x in range(im.size[0]):

            #Get a new RGB tuple based on thresholds
            new = []
            for c in range(3):
                color = img[x, y][c]
                level = bisect_left(thresholds, color)-1
                new.append(thresholds[level])

            #Put the new pixel on the image
            img[x, y] = tuple(new)
    
    #Return the image
    return im

Anyway, can someone explain why this returns green pixels, and how to fix it? If possible, I would like to still use an approach similar to mine, if possible. Thanks in advance.

Answer 1

You're using bisect_left almost correctly... almost.

If you read the documentation, you'll notice how bisect takes lo and hi parameters, which are set to 0 and len(arr) respectively. To work around IndexError, you add -1 to the result. But this will map results that should be 0 to len-1, since indexing arr[-1] in Python is the same as indexing arr[len(arr)-1]. And indeed, if you look closely - the green pixels should have their green channel set to 0, but they get 255 because of the -1 wraparound.

That is the source of your green pixels.

The fix is simple - instead of doing:

bisect_left(thresholds, color)-1

do

bisect_left(thresholds, color, lo=0, hi=len(thresholds)-1)

and that's all. At the same time, you'll notice how the pictures have their brightness set correctly as well, since because of -1 the are darker than they should be.