For my Spotify DBus project, I’m looking at ways to extract the dominant(s) colors from an image, in this case an album cover. I simply want to fill the background with a nice color, dynamically.
Like starting any good research rabbit-hole, converting my abstract goal to a searchable query (with proper terms of art) takes some reflection:
I first came across this StackOverflow post where the OP shared a similar goal. The replies reminded me that /clustering/ is a term that exists.
I was reminded of this YouTube video (timestamp 9:15) discussing how to simplify Minecraft texture palettes using Mean Shift Clustering. The video does not explain it, but I think the algorithm terminates when no more clusters can be added— i.e. every color is in a cluster. The video also does not explain where a new cluster is initialized. Assuming it’s random, that is also my issue with the famous K-means algorithm. Yes, the bulk of the algorithm is deterministic, but the crucial step of initialization is random, thus producing different outputs for the same input. There are also concerns if input order is significant.
I eventually came across this paper: Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering. It looks like a nice approach. Their technique takes inspiration from histogram partitioning in image processing.
I landed on some image processing textbook: Basics of Image Processing. And then took a quick detour into Image Segmentation: Thresholds and Color Spaces. I started to wonder if color segmentation was a thing, but was turned off because image segmentation seems more for spatial boundaries.
I somehow ended up on Color quantization which is reducing the number of colors in an image. I was still a bit iffy on this technique because the number of resultant colors is still relatively large (~16). The article referenced an obscure method using octrees. This method constructs on octree where the the child index of a node is an octal digit corresponding to the most significant bit of each channel R, G, and B: chmod). The quantization actually occurs by reducing each child node up to it’s parents, leveraging the fact that the MSB is at the root.
E.g: In a 12-bit RGB space: A parent at index 356_ ([2,5,4]. Those children get reduced so now [3562, 3565, 3564] (356_.
This old article and this 2016 paper are also good references.
I was still looking for methods to extract a handful of dominant colors, and came across this StackOverflow post that pointed me towards Google/Android’s Material Color Utilities. A couple of years ago, the Material Design System was overhauled to be centered around Material You. A core part of this design ecosystem was allowing custom color palettes, color schemes, and themes that could be easily generated (usually from a wallpaper). I’ve always wondered about the color science of their research and implementation, but the first step in the process, which they call “Quantize”, is based on a 1991 article Efficient Statistical Computations for Optimal Color Quantization and a 2011 paper Improving the Performance of K-Means for Color Quantization.
Underlying all of this is me wondering if RGB-defaultism will be my downfall. I’m sure using one of the fancy new colorspaces is conducive towards deciding a “dominant” color.