Generate a color palette from an image using k-means clustering.

Have you ever seen the images floating around that show the color palettes from various scenes of visually striking movies? Well now you can create some images of your own using this script! The script uses a process called k-means clustering to generate a color palette from the image.

The script creates two versions of the original image: one with a color swatch at the bottom and one with the pixels in the image replaced with their closest color from the palette. The script will also plot all the pixels in 3D space based on their RGB values and show the clusters by coloring them based on their closest color from the palette.

To easily run the code in your browser and avoid having to install dependencies, you can use this Google Colab Notebook: https://colab.research.google.com/drive/1WkfTnGPPqsvJdV8SHu_zw3rnY21pIehT?usp=sharing

All the code for this project can be found here: https://github.com/mjdargen/tutorials/tree/main/color_palette

The source code also contains a modified script from GitHub user v-za to download still images from movies from https://film-grab.com. See their original script here: https://github.com/v-za/film-grabber.

Step 1: Running Script With Google Colab

Intro to Colab

Google Colaboratory is a Python development environment using Jupyter Notebooks that allows you to connect to Google’s powerful cloud computing resources and run Python code. It allows you to maintain a runtime environment where you can install packages, access data online, navigate a file system, and store/reuse data.

If you would like to avoid having to install the dependencies on your machine, you can use the Google Colab Notebook I have provided. Using the free cloud-computing resource will help you avoid burdening your own processor.

Executing Code in Colab

There are two different types of cells: code & text. Text cells are used to describe what's going on. Code cells can be executed one at a time by clicking the play button.

Notebook Overview

Color Palette Google Colab Notebook: https://colab.research.google.com/drive/1WkfTnGPPqsvJdV8SHu_zw3rnY21pIehT?usp=sharing

This program will take an image from Google Colab or directly from https://film-grab.com. It will then output the images into a zip file. The Colab notebook is broken up into the following steps:

Clone Scripts from GitHub
Configuration Options
Retrieve Files
Run Script
Output
Color Palette Image
Replaced Colors Image
3D Pixel Plot
Download Output

The Google Colab notebook contains full instructions for how to run each cell.

Step 2: Setting Up Environment to Run Locally

In order to run the code required for this project locally, you will need to install Python 3 and git. The installation steps can vary slightly based on your operating system, so I will link you to the official resources which will provide the most up-to-date guides for your operating system.

Git Project Files

Now you will need to retrieve the source files. If you would like to run git from the command line, you can install git by following the instructions here: https://git-scm.com/book/en/v2/Getting-Started-Installing-Git. However, you can just as easily download the files in your browser.

To download the files required, you can navigate to the repository in your browser and download a zip file or you can use your git client. The link and the git command are described below.

https://github.com/mjdargen/tutorials/tree/main/color_palette

git clone https://github.com/mjdargen/tutorials.git

Installing Dependencies

You need to install the following programs on your computer in order to run this program:

Python 3 with pip: https://www.python.org/downloads/
Install Pillow, plotly, and beautifulsoup4: `pip3 install -r requirements.txt`

Step 3: Running Film Grabber Script

This script is a modified version of GitHub user v-za script to download still images from movies from https://film-grab.com. See their original script here: https://github.com/v-za/film-grabber.

To run the film grabber script, use the following command: python3 filmgrabber.py -f <film> -p <path>

-f <film> - Name of the film to search for. Exp: Blade Runner 2049
-p <path> - Output file path to store images. Exp: ./stills

To see the full list of the films that they have available, go to this page: https://film-grab.com/movies-a-z/

Step 4: Running Color Palette Script

To run the color palette script, use the following command: python3 palette.py -i <image> -k <kcolors> -l <limit>

-i <image> - Path to image file. Exp: ./bladerunner001.jpg
-k <kcolors> - K value i.e. number of colors in palette. Exp: 6
-l <limit> - Max number of iterations to test convergence. Exp: 20

Step 5: P Vs. NP

To generate a color palette, we will need to cluster colors together. Clustering points together in multidimensional space is classified as an NP-hard problem. An NP-hard problem is a class of problem that essentially cannot be definitively solved by a computer. This refers to the P vs. NP problem in computer science and math, which is one of the biggest and most difficult unanswered questions. In fact, if you solve this question, you will be awarded $1 million by the Clay Mathematics Institute in 2000.

Essentially, "P" refers to a general class of questions for which some algorithm can provide an answer in polynomial time. These are contrasted with "NP" questions, which stands for "nondeterministic polynomial time". These questions cannot be solved in polynomial time. However, if you are provided an answer to an NP question, it is easy to verify that answer in polynomial time.

A good example of an NP problem is Sudoku. If I provide a solution to a Sudoku puzzle, an algorithm can pretty easily verify whether the solution is correct or not. However, if I ask an algorithm to solve a Sudoku puzzle, it becomes exceedingly more difficult especially as the size of the grid grows. For more information on P vs. NP, watch the video linked above.

Step 6: K-means Clustering

I already established that clustering points together in multidimensional space is a problem for which there is no determinant answer at the present moment when it comes to algorithms. However, we are going to use a process called k-means clustering to use heuristics and find local optimum that should hopefully satisfy our use case.

Now why am I talking about multidimensional space when it comes to an image? That is because we are going to plot each component of a pixel (red, green, blue) into three-dimensional space. By plotting these points into 3D space, we can better visualize how we can cluster these points together to find commonalities to construct a color palette.

This process is called k-means clustering because from some number of points, we will find k number of clusters in which each point belongs to the cluster with the nearest mean. To do this, we will randomly select k pixels to serve as our original mean point or centroids. We will then create k number of clusters by iterating through each pixel and determining which centroid is the closest. After iterating through all pixels, we will find the mean of each cluster. These means will become our new centroids. We will repeat this process of clustering the pixels and finding the new centroids until the centroids converge i.e. the centroids no longer change after clustering.

Step 7: How It Works

main() opens the image and randomly chooses k pixels to serve as the starting centroids. There is then a while loop that repeats the clustering process until convergence has been reached. converged() is responsible for determining whether the centroids have converged or not by comparing the new centroids with the previous centroids. Absolute convergence may not be reached, so there is a max number of iterations that is set to prevent the script from running endlessly.

cluster_pixels() is responsible for iterating through all the pixels and finding the closest centroid for each and assigning the pixel to a cluster. cluster_pixels() calls get_min() to find the closest centroid by computing the 3D distance vector from the pixel to each of the centroids. After clustering is complete, compute_centroids() is called to compute the new centroids based on the mean of the resulting clusters. If convergence is not reached, the process is repeated.

Once convergence is reached, there are three outputs from the program. draw_palette_image() creates the output image with the color palette of the centroids shown at the bottom. draw_replaced_image() creates the output image with each pixel replaced with its cluster's centroid color. plot_pixels() generates a 3D scatter plot of all the pixels showing the clusters.