Algorithm challenge: Generate color scheme from an image

Background

So, I'm working on a fresh iteration of a web app. And, we've found that our users are obsessed with being lazy. Really lazy. In fact, the more work we do for them, the more they love the service. A portion of the existing app requires the user to select a color scheme to use. However, we have an image (a screenshot of the user's website), so why can't we just satiate their laziness and do it for them? Answer: We can, and it will be a fun programming exercise! :)

The Challenge

Given an image, how do you create a corresponding color scheme? In other words, how do you select the primary X colors in an image (where X is defined by the web app). The image used in our particular situation is a screenshot of the user's website, taken at full resolution (e.g. 1280x1024). (Note: Please simply describe your algorithm - there's no need to post actual pseudocode.)

Bonus points (street cred points, not actual SO points) for:

• Describing an algorithm that is simple yet effective. Code is how we create - keep it simple and beautiful.
• Allowing the user to tweak the color scheme according to various 'moods' such as 'Colorful', 'Bright', 'Muted', 'Deep', etc. (a la Kuler)
• Describing a method for reliably determining the main text color used in the website screenshot (will likely require its own, separate, algo).

Inspiration

There are several existing sites that perform a similar function. Feel free to check them out and ask yourself, "How would I duplicate this? How could I improve it?"

• http://www.pictaculous.com/
• http://www.cssdrive.com/imagepalette/index.php
• http://kuler.adobe.com/#create/fromanimage

1. To find the primary X colors, screencap the app. Run a color histogram on the image. The top X colors in the histogram are the theme. Edit: if gradients are used, you'll want to pick distinct "peaks" of colors; that is, you may have a whole bunch of colors right around "orange" if orange is one of the main colors used in the gradients. Effectively, just enforce a certain amount of distance between your colors chosen from the histogram.

2. Tweaking the color scheme can best be done in HSV space; convert your colors to HSV space, and if the users want it to be "Brighter", increase the Value, if they want it to be more "Colorful", increase the Saturation, etc.

3. Determining the text color can best be done by characterizing areas of high variability (high frequency in Fourier space). Within those areas, you should have either: two colors, text and background, in which case your text is the lesser-used color; or you'll have several colors, text and background image colors, in which case the text color is the most common color.

You can take a look at:

https://github.com/dcollien/Dreamcoat

which does this in CoffeeScript (literate coffee, so it's well documented)

Demo here: http://dcollien.github.io/Dreamcoat/test.html

It has both a colour quantization approach, and a KMeans approach which are combined.

I do this to find the palette used for images (of artwork).

1. I start with imagemagick and resize a large image down to a workable size (i.e. 400 px on largest dimension.) This actually helps convert subtle local color differences into fewer pixels with an average of those colors.

2. Loop through each pixel present in the resized image, reading the RGB values for each pixel, convert the RGB to HSB and store the HSB values to an array.

3. For each pixel color found, I then divide the Hue range (0,255) by 16, the Saturation range (0,100) by 10, and Brightness range (0,100) by 10. Round the result up or down to an integer. This helps group pixels into categories of similar colors.

So a pixel with HSB of 223,64,76 would be in the category 14,6,8

Within each category, you can still find the exact color of each pixel, but for the most part the categories themselves are a close color match to the source image.

Choose to divide the HSB into finer divisions if you want better color replication from the categories. ie. divide each H,S,B by 8,5,5 instead of 16,10,10.

1. Count up the most prevalent color categories, sort and display. I discard color categories with very few pixel counts.

Note: This is really designed for artwork that has very few pixels with identical color values (i.e. paintings with shadows and gradients.)

For the most part, an HTML page probably has more pixels that exactly match a specific color value (i.e. background color, text color, etc. are all going to be the same color wherever they appear.)

Color quantization is the same process used to choose the palette for low-color GIFs. To get a color palette from a photographic image, I used Nick Rabinowitz’ quantize.js which is based on Leptonica’s MMCQ (modified median cut quantization).

Live web app, about.

1. Divide the screen image into a grid of r-many rectangles, in an n by m "grid", each with width (total width / n) and height (total height / m).

1a. Assign a weight to high-profile areas of the screen, such as the left-off-center area.

1b. For each rectangle, assign the pixels into a space of (color,frequency)

2. For each rectangle R, frequency distribution f_R, and weight W_R:

2a. Determine the i-th scheme color (e.g. i = 1 <--> background color) by scanning the "top frequency", "second frequency" (i.e. f_R[i,:]) for each block.

2b. For each i, put it in a score table, (color_i,score) where score = f_R[i,"frequency"] * W_R

2c. The top scorer for each i will be the i-th scheme color.

Theoretically, if you have a lot of "blue on white" or "red on black", you should get white primary, blue secondary, or black primary, red secondary, for example.

For your text color, either base this directly on a calculation off of background color, or choose secondary color, and if the V difference of HSV is too low, base the color off of the computed scheme color, but augment the V value.

PseudoCode:

float[][] weights = 
    { { 1.0, 3.0, 5.0, 5.0, 3.0, 1.0, 1.0, 1.0, 1.0 },
      { 2.0, 6.0, 7.0, 7.0, 6.0, 2.0, 3.0, 3.0, 2.0 },
      { 2.0, 8.0, 9.0, 9.0, 7.0, 3.0, 6.0, 6.0, 3.0 },
      { 2.0, 8.0, 9.0, 9.0, 7.0, 2.0, 3.0, 3.0, 2.0 },
      { 2.0, 7.0, 9.0, 9.0, 7.0, 2.0, 1.0, 1.0, 1.0 },
      { 2.0, 6.0, 7.0, 7.0, 6.0, 2.0, 3.0, 3.0, 1.0 },
      { 1.0, 3.0, 5.0, 5.0, 3.0, 2.0, 6.0, 6.0, 2.0 },
      { 1.0, 1.0, 2.0, 2.0, 1.0, 2.0, 6.0, 6.0, 2.0 },
      { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 3.0, 3.0, 1.0 } };

// Leave the following implementations to the imagination:
void DivideImageIntoRegions( Image originalImage, out Image[][] regions );
void GetNthMostCommonColorInRegion( Image region, int n, out Color color );
TKey FindMaximum<TKey, TValue>( Map<TKey, TValue> map );

// The method:
Color[] GetPrimaryScheme( Image image, int ncolors, int M = 9, int N = 9 )
{
    Color[] scheme = new Color[ncolors];
    Image[][] regions = new Image[M][N];
    
    DivideImageIntoRegions( image, regions );
    
    for( int i = 0; i < ncolors; i++ )
    {
        Map<Color, float> colorScores = new Map<Color, float>();

        for( int m = 0; m < M; m++ )
        for( int n = 0; n < N; n++ )
        {
            Color theColor;
            GetNthMostCommonColorInRegion( region, i, theColor );
            
            if( colorScores[theColor] == null )
            { colorScores[theColor] = 0; }
            
            colorScores[theColor] += weights[m][n];
        }
        
        scheme[i] = FindMaximum( colorScores );
    }
    
    return scheme;
}

Looking at the above, it's clear that if there is a region with little variability, it will have the same second-most-common color as most-common color. To adjust, the second-most-common color in such a case might be null, which one could guard against:

            if( theColor != null )
                continue;
            
            if( colorScores[theColor] == null )
            { colorScores[theColor] = 0; }
            
            colorScores[theColor] += weights[m][n];
        }

The name of the type of algorithm you want is Color Quantization.

Unfortunately I don't have any source code available for you, but I'm sure a google search could turn something up.

In particular, the Dr. Dobb's Journal article on the subject seems promising.

Similar to McWafflestix's solution, the specifics will need to be tweaked, but my general approach would be...

(I agree that HSV is the right space)

1. Grab a histogram of the image, filter it to smooth the noise, and find the highest score where V and S are in a (possibly dynamic) gamut of likely "subject" colors. A red bird on a blue sky will require that we be smart enough not to base our scheme on the blue, but on the red. This may require some guesses about photo composition, like "centered in the frame" and "rule of thirds" analysis could give you a probability of a color being relevant. Regardless, this is our the base color.

2. Along the lines of Kuler, calculate colors that compliment the base by moving around the color wheel. Extra points for a calculated compliment if it also appeared prominently in the histogram from step 1.

3. Use the base color and calculated compliments to derive pleasing adjunct colors, such as lighter and darker versions of each, more or less saturated, etc.

There are already a lot of good suggestion how to find the primary colors and I would try similar approaches. For finding the text color, I have another suggestion.

Calculate the histogram for each line in the image from top to bottom. Every time you reach the base line of a line there should be a strong drop in the frequency of the text color. The frequency will remain low until you reach the upper case letters of the next line followd by a second step when you reach the lower case letters.

If there is another strong peak that becomes even larger when you hit the base line, you have found the background color. A gradient background will smooth this peak and the changes of the peaks - when you enter or leave a new line - will be smoothed by antialiasing.

Below are some suggestions and discussion around different approaches for generating a color scheme from an image:

First, embed/plot your pixels in some color space. This can be RGB, HSL, or some other color space. Then you can use one of the following to generate a color scheme:

1. Creating a histogram of the color space - This involves splitting the space into a grid, and counting the pixels in each grid cell. Select the top N cells (histogram buckets) with the most pixels, and average the pixels in each to produce a color per cell. This can be your color scheme.

2. Median Cut or some other space partitioning technique - This is a nice improvement over #1, as it will split the space by looking at the data.

3. Clustering Pixels - Cluster the pixels into groups using one of many clustering techniques (k-means, mean-shift, etc.). Then average the pixels in each group to generate a color scheme.

I wrote a more detailed post on the three above approaches here

I also wrote an interactive web app that allows you to load an image an create generate a color palette using one of the above three approaches. You can find the code for it on github

I'm a bit late to this, but I would implement a Kohonen Map (http://en.wikipedia.org/wiki/Self-organizing_map) in a 3d colour space. The number of points on the map would be the number of distinct colours you wanted for your palette, then train your map using all of the pixels from the image. I've not tried this myself but I'm sure someone else has thought of it already.

Average the hue, saturation and brightness separately while keeping the min/max values.

Lock the target hue of all the colours to the average and interpolate the saturation and brightness for the x points between the boundaries. This should return a scheme with a colour cast the same as the foto but with a simple variation. Maybe you'll even get the Apple look.

Just hope you don't get 3 shades of dog puke.