The most obvious way to implement something like this is to just histogram the pixels and sort by most popular, it's like literally 4 lines of Python:
# Find the n most popular colors in the array of pixels
def most_popular_colors(pixels, n):
count = {}
for i in range(len(pixels)):
count[pixels[i]] = count.get(pixels[i], 0)+1
return sorted(count.items(), key=lambda kv : kv[1], reverse=True)[:n]
Any image that's a photo, or uses a gradient, or has ever been JPEG or MPEG compressed, is going to have a ton of fine variations in its colors. All the pixels of "that shade of green" aren't going to be exactly #123499, some of them are going to be #133499 or #123498 or something. A simple histogram like the above code will tally all those distinct colors separately.
So you can get a most-popular list containing multiple very, very similar shades that are technically distinct integers. And you can have a color that "should" be on the most-popular list but isn't, because it's a bunch of very subtly different shades, none of which has a high enough count to crack the list.
Which means to get the behavior the users expect, a simple histogram simply won't do. You need additional logic to "bucket" similar colors together for the counting part, and then show a "representative" of the most popular buckets for the final output.
How are the buckets defined? How are the representatives selected? There are probably a dozen different reasonable implementation choices you could make. Different choices will all give slightly different (or even very different) outputs.
I would actually be very surprised to find two independently written programs would give the same output for this problem, and I would suspect they're not actually independent (i.e. they both used the same software or both found the same textbook or RFC or whatever that suggests very specific implementation choices.)
To create the palette, we took 10k random product images from our catalog, cropped them to the center 1/3, and stitched them into a single image collage. Then we used imagemagick to quantize it to 64 colors to produce our palette.
The extract colors for a given image, we’d crop to center, quantize using the above palette and then run the histogram.
K-means clustering seems to have a good tradeoff between performance and results. Interestingly, I found that when doing this in the RGB color space you'd get dominant colors that seemed off. They were usually too dark or muddled.
The best option I found was using k-means clustering in the LAB color space. So you convert the image to RGB, convert that to LAB, run k-means, then pull out the biggest clusters. I don't know enough about color theory to really explain why this works so well, but there are plenty of papers and research on it.
I was also considering using DBSCAN or a different algorithm, but most other clustering algorithms are significantly slower. I personally wonder what programs like Spotify and iTunes use to find the dominant color for something like album art, but I assume they cache the result of the best clustering algorithm they have, potentially even including human input at some point in the process.
Color is complicated.
- RGB is as simple but error-prone model for human color reception
- Human color reception is not linear and extremely lossy
- Color reception strongly depends on lighting and our vision autocorrects distortions
- Monitors and prints have their own quirks
As far as I know LAB color space tries to account for these facts. It doesn't surprise me that you found out that it worked better than other color models.
from collections import Counter
def most_common_colors(pixels, n):
return Counter(pixels).most_common(n)I've done this using k-nearest neighbors to cluster colors of an image into n "modes". I was building a toy app to take a photo with your phone to select a color. Like a really, really dumb color wheel UI basically.
In my case, using something like CIELAB or Oklab also helped, to better cluster colors into human perception bins.
