5 ms·

It would be nice if there was some acknowledgement of previous work in this area like the median cut algorithm http://en.wikipedia.org/wiki/Median_cut http://en

It would be nice if there was some acknowledgement of previous work in this area like the median cut algorithm http://en.wikipedia.org/wiki/Median_cut http://en.wikipedia.org/wiki/Median_cut the neuquant algorithm http://members.ozemail.com.au/~dekker/NEUQUANT.HTML http://members.ozemail.com.au/~dekker/NEUQUANT.HTML or the dozens of other image to palette services a google search away (including one that google uses itself for image search) So, maybe an explanation of why this is better than those, different from those, a comparison of sorts. Or would it be better if some third party did this "benchmarking" work eh? specifically, I am concerned that this approach is based on tiny micro-heuristics based on specific images and not a robust statistical model of human perception. edit: here's another (I may use this comment to continue collecting existing algorithms) http://www.springerlink.com/content/f002412013877333/ http://www.springerlink.com/content/f002412013877333/

dhotson 14y ago
We haven't really looked too deeply into existing research in this area, so I'm not sure how our approach compares. We'd still be very interested if you've got any suggestions for material to check out. One difference between our program and other general purpose quantization algorithms is that we wanted to optimise for logo designs and images with flat shapes and colors (as opposed to photos with millions of colors). We also wanted to get something working quickly so that we could get onto some large scale color analysis stuff (which we'll hopefully be writing about soon). There's definitely room for improvement in the color extraction process.
- ZenPsycho 14y ago
  One thing I would like to research is the fact that once you map colors into lab space you end up with a point cloud with clusters around the primary colors. the problem then becomes using AI techniques to find the "peaks" in this data, and finding how the results from that step statistically match up to human perception of primary colors. This ends up being a similar problem to signal processing the output from a capacitive touch screen. The processor at a low level simply receives a 2D capacitance image from which it must extract the center points of fingers and their sizes- And there is a broad range of literature to find on this more generalized problem of "peak detection".
- ZenPsycho 14y ago
  incidentally I'm pretty sure you and I are in the same city, given that I used to work at the same company as you.
  - dhotson 14y ago
    Oh?
    - ZenPsycho 14y ago
      sitepoint
mrmaddog 14y ago
I feel like k-means in in Lab color space would lend itself well here too. Either by picking a large k that you then narrow down by picking the highest contrast colors, or instead by running k-means multiple times with different k's until you get an error threshold that is tolerable and results that have a high enough contrast. K-means is also a pretty easy algorithm to understand/implement.
- joshu 14y ago
  that's what i was thinking, as well. of course the problem with k-means is figuring out the number of clusters...
- dhotson 14y ago
  We haven't tried clustering yet, but I'm keen to. Correct me if I'm wrong, but by using clustering you might end up with colors that didn't actually occur in the original design right? In our case we wanted to make sure we found colors that the designer actually chose. I'll have to try this..
  - isani 14y ago
    K-means clustering gives you a set of centroids which are the calculated means of each cluster. If you only want actually occurring colors, just look up the color closest to each centroid.
- drifkin 14y ago
  Google uses k-means clustering in Chrome on their new tab page (though they use RGB). The most visited section shows a color strip below each site, with a color chosen from the site's favicon. Here's the code: http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis.cc http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis....
  - drifkin 14y ago
    It turns out the header file actually has a pretty nice explanation of the algorithm: http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis.h http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis....

dhotson 14y ago

We haven't really looked too deeply into existing research in this area, so I'm not sure how our approach compares. We'd still be very interested if you've got any suggestions for material to check out. One difference between our program and other general purpose quantization algorithms is that we wanted to optimise for logo designs and images with flat shapes and colors (as opposed to photos with millions of colors). We also wanted to get something working quickly so that we could get onto some large scale color analysis stuff (which we'll hopefully be writing about soon). There's definitely room for improvement in the color extraction process.

ZenPsycho 14y ago
One thing I would like to research is the fact that once you map colors into lab space you end up with a point cloud with clusters around the primary colors. the problem then becomes using AI techniques to find the "peaks" in this data, and finding how the results from that step statistically match up to human perception of primary colors. This ends up being a similar problem to signal processing the output from a capacitive touch screen. The processor at a low level simply receives a 2D capacitance image from which it must extract the center points of fingers and their sizes- And there is a broad range of literature to find on this more generalized problem of "peak detection".
ZenPsycho 14y ago
incidentally I'm pretty sure you and I are in the same city, given that I used to work at the same company as you.
- dhotson 14y ago
  Oh?
  - ZenPsycho 14y ago
    sitepoint

mrmaddog 14y ago

I feel like k-means in in Lab color space would lend itself well here too. Either by picking a large k that you then narrow down by picking the highest contrast colors, or instead by running k-means multiple times with different k's until you get an error threshold that is tolerable and results that have a high enough contrast. K-means is also a pretty easy algorithm to understand/implement.

joshu 14y ago
that's what i was thinking, as well. of course the problem with k-means is figuring out the number of clusters...
dhotson 14y ago
We haven't tried clustering yet, but I'm keen to. Correct me if I'm wrong, but by using clustering you might end up with colors that didn't actually occur in the original design right? In our case we wanted to make sure we found colors that the designer actually chose. I'll have to try this..
- isani 14y ago
  K-means clustering gives you a set of centroids which are the calculated means of each cluster. If you only want actually occurring colors, just look up the color closest to each centroid.
drifkin 14y ago
Google uses k-means clustering in Chrome on their new tab page (though they use RGB). The most visited section shows a color strip below each site, with a color chosen from the site's favicon. Here's the code: http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis.cc http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis....
- drifkin 14y ago
  It turns out the header file actually has a pretty nice explanation of the algorithm: http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis.h http://src.chromium.org/svn/trunk/src/ui/gfx/color_analysis....