Extracting the Color Palette from an Image in Rust (color quantization)

Working with images has always seemed like a fascinating topic to me for several reasons: it's visual, it's an optimization challenge, you work with matrices... Specifically, I was drawn to an algorithm to summarize the colors of an image and extract the most important ones: color quantization using an octree.

Nowadays, an image has millions of pixels with a lot of information. There are all kinds of lossy and lossless compression algorithms (JPG, PNG, etc.) that allow us to reduce the size of an image.

The human eye is not capable of perceiving the subtleties of a RAW image, so if two very similar colors are approximated to the same one, even though you lose some precision, to a person’s eyes, the colors will be the same. Obviously, the more colors you approximate, the worse the quality of the image, so the key is to find the middle ground.

The technique that extracts the most important colors from an image is known as color quantization. I found this article from 1997 (I had been in the world for a short time) that talks about how to calculate these colors using an octree, which involves transferring the RGB colors to three-dimensional space and using an Octree, which is essentially a tree with 8 branches, to group them and then gradually eliminate leaf nodes until we are left with the most representative colors.

We are essentially generating a color palette and then mapping the pixels of the original image using this palette to reduce the amount of information.

I was keen to continue learning Rust and try to implement this algorithm for fun. Below I show you an example of the result of an image of the Alhambra for different palette sizes:

Algorithm Theory

The idea of the algorithm is to transfer each pixel to a three-dimensional space. This is done using the following technique: given an RGB pixel with values in the range [0, 255], each value is an 8-bit integer. Let's take the following example #33CCFF:

• R = 33 (hex) = 51 (dec) = 00110011 (binary)
• G = CC (hex) = 204 (dec) = 11001100 (binary)
• B = FF (hex) = 255 (dec) = 11111111 (binary)

The original octree algorithm groups the 3-bit values vertically: 011, 011, 101, 101, 001, 011, 011, 101, 101, which form the pixel. Since each value is a number from 0 to 7 (8 values), each value represents the index of the octree node until reaching the leaf node, where we store the color.

To obtain these values, you have to work with bit operators: for example, you can shift the bits to the right N times with the >> operator and then get the desired bit by applying a mask 00000001.

For example: (00110011 >> 7 - i) & 00000001 for i in the range [0, depth].

Finally, we traverse the tree at one level and add the colors in the leaf nodes by calculating the average.

In my case, I implemented it differently, using a Hash based on depth. In the example for depth 4, I get the hash of the values 011, 011, 101, 101 = 3355. This way, in a hash table, I store the sum of the colors that share this hash. Thus, with depth, you limit the colors of the palette to base 8. In the next section, I will tell you more about this.

Why Rust

Rust is a language that we can't deny is trendy. In my case, there are trends I like, and others not so much. In this case, the idea behind Rust seems interesting to me, and seeing the community's reception and the emergence of important projects in Rust, the best thing is to try it and be able to give an opinion.

A couple of years ago, I started studying Rust to try it out in side projects like this one. The learning curve is tough at first because the famous borrow checker forces you to think differently than you would with other languages. It's an interesting concept but requires time.

Nowadays, I find it comfortable to work with this language, besides being very efficient, although there are still more complex challenges that I don't know how well they would be addressed with this language and if doing them in another language like C/C++ would be simpler. However, I am beginning to see a movement against unsafe languages, which I don't know how it will end, and personally, I still don't have an opinion about it. We will see over time.

In any case, it is a low-level language that allows you to write efficient code and has other advantages that make me want to learn it. However, for scripts, I will always use Python, and for developing quick and efficient code, I love Go and its goroutines and channels. But it never hurts to learn how other tools work.

My Implementation

You can access the code in the GitHub repository.

Implementing a Tree in Rust is a very interesting topic because it mixes concepts of references and the lifetimes of variables, but this time it can be implemented much more simply.

The idea is to get the hash of a pixel with the desired depth and use a Map<String, [count, r, g, b]> to store all the pixels that have the same hash for a given depth.

For example, the color white [255, 255, 255] = 7777777 (depth = 8) = 7777 (depth = 4)...

This way, we simplify the process of creating an octree, and simply with the hash and limiting its size to a depth, we add all the colors very similarly to how a tree would, thus avoiding all this complexity.

For each depth level, we have 8 values, so the color palette will be at most 2^(3*depth).