Comment by csense | Hacker News Reader

Comment by csense | Hacker News Reader

This is not too surprising.

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]

This works (for some definition of "works"), but it doesn't do what users expect. They will probably complain a lot about the results.

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.)

We had to do this at Polyvore (a fashion e-commerce site) to extract dominant colors from products.

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.

That's interesting. What was the use case? (why extracting colors?)

The extracted colors were used in a few different ways:

1. product search - show me "red" shirts.

We also mapped certain hues to "saturated", "muted", "pastel" etc... meta colors based on HSV values. Unfortunately, we never got to surfacing these meta colors as search facets.

2. similar product recommendations - show me shirts similar to this one. colors (and meta colors like "muted") were one of the features used in similar product recs.

3. analytics - turquoise is "trending"

I incorporated logic for finding dominant colors into a program I had written, and from my research clustering algorithms were the best way to get the dominant color in a way that most users would expect.

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.

> 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.

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.

Nitpick about the counting. It's actually even easier!

  from collections import Counter
  
  def most_common_colors(pixels, n):
      return Counter(pixels).most_common(n)

> 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'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.

Weird. I always thought of this task as the most natural use-case for KNN.

Reply on news.ycombinator.com