Palette Swap (1NN-algorithm)

I created a simple algorithm that can take in an image and change the colours of the image to fit a palette in python using NumPy.

How it works

The 1- Nearest Neighbour (1-NN) algorithm is a classical machine learning algorithmn, therefore, like all ML it uses Linear Algebra.

K - NN

The K Nearest Neigbour algorithm is a simple algorithm for classification. It takes an vector of an unkown, a list of values, and compares it the vectors of classes it does know. This works as vectors can be imagined as positions in a high dimentional space. It looks to the nearest K classes closest to the unkown vector, and assigns it the class of the most popular class found it the nearst K class. In my case, since each of the known vectors are their own class, pixels in a pallete, it just looks to the nearest vector and turns into the vector, essentially turning a random pixel into the pixel of the pallete most similar to it.

Pixels

Using the pillow library from my last post, I turned the png into RGB, and then from there converted it into a NumPy tensor of shape [Height, Width, RGB]. This means that the tensor is a 2d array where tensor[n][m] stores the RGB values / vectors in the form [R,G,B]. But to make this more simple for calculations, I collapsed height and width into a long list of [Pixels, RGB]

I also made a palette list containing some [R,G,B] pixel values. Initially I just used the engesda 64 pallete.

Broadcasting and Normalisation

Now that I had my 2 tensors (palette and pixels), I can employ the algorithm. Before I calculate the distances, I need to first change these two tensore using broadcasting. Broadcasting is a NumPy mechanic where you add extra dimentions to operate with. Currently I have 2 tensors, pixels [pixel, RGB] and pallete [colour, [RGB] and I want the combined tensor to be in the shape [pixel, colour, RGB], so for each pixel I calculate the distance from the pixel’s RGB to the RGB of each of the palletes colour. To make this happen I used broadcasting, adding one extra dimention to both the pallete and pixel tensors, before subtracting the values.

Now that I had the distance vectors, I converted each [R,G,B] values into its magnitude (sqrt(R^2 + G^2 + B^2)) to turn the distance of a pallete colour to the pixel into one number. Then I chosed the pallete colour with the lowest distance and converted the initial pixel to this colour.

Conclusion

In this part I learnt a lot about how to use NumPy and it’s broadcasting feature and changed the palette of the bird image from my last post to these 3 images: