Algorithm challenge: Generate color scheme from an image

Question

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

Have fun! :)

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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];
        }

Answer 6

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.