Algorithm task: to form a color scheme from the image

Question

Background

So, I am working on a new iteration of a web application. And we found that our users are obsessed with the lazy. Really lazy. In fact, the more work we do for them, the more they love the service. Part of an existing application requires the user to select a color scheme for use. However, we do 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 fun programming! :)

A task

For an image, how do you create an appropriate color scheme? In other words, how do you choose the primary colors of X in the image (where X is defined by the web application). The image used in our particular situation is a screenshot of the user's website made in full resolution (for example, 1280x1024). (Note. Please just describe your algorithm - there is no need to publish the actual pseudo-code.)

Bonus points (street credit points, not actual maintenance points) for:

• Description of a simple but effective algorithm. Code is how we create - we keep it simple and beautiful.
• Allows the user to customize the color scheme according to various “moods” such as “Color”, “Vivid”, “Muted”, “Deep”, etc. (a la Kuler )
• Description of the method for reliable determination of the main color of the text used in the screenshot of the website (most likely, it will 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 will 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

Answer 1

• To find the primary colors of X, browse the app. Run a color bar chart in the image. The main colors of X in the histogram are the theme. Edit: if gradients are used, you need to select different “peaks” of colors; that is, you can have a whole bunch of flowers right around the "orange" if orange is one of the primary colors used in gradients. Effectively just impose a certain distance between your colors selected from the histogram.

• Fine-tuning the color scheme is best done in the HSV space; convert your colors to HSV space, and if users want it to be brighter, increase the value, if they want it to be more color, increase saturation, etc.

• Text color determination is best done by characterizing areas of high variability (high frequency in Fourier space). In these areas, you should have either: two colors, text and background, in which case your text is a smaller color; or you will have several colors, text and background image colors, in which case the text color is the most common color.

Answer 2

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

• I start with imagemagick and resize the large image to the working size (i.e. 400 pixels to the largest size). This actually helps to convert subtle local color differences to fewer pixels with an average of these colors.

• Scroll through each pixel in the resized image by reading the RGB values ​​for each pixel, convert RGB to HSB, and save the HSB values ​​to an array.

• For each pixel color found, I then divide the hue range (0.255) by 16, the saturation range (0.100) by 10, and the brightness range (0.100) by 10. For the sake of the round, the result is an up or down integer. This helps to group pixels into categories of similar colors.

  So, the pixel with HSB 223.64.76 will be in the category 14.6.8

  In each category, you can still find the exact color of each pixel, but for the most part the categories themselves are close in color to the original image.

  Choose to divide HSB into smaller divisions if you need better color replication from categories. i.e. divide each H, S, B by 8.5.5 instead of 16.10.10.

• Count the most common color categories, sorting and display. I drop color categories with very few pixels.

Note. This is really intended for works of art that have very few pixels with the same color values ​​(for example, with shadows and gradients.)

For the most part, an HTML page may have more pixels that exactly match a particular color value (for example, background color, text color, etc. all will be the same color if they appear).

Answer 3

You can take a look at:

https://github.com/dcollien/Dreamcoat

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

Demo here: http://dcollien.imtqy.com/Dreamcoat/test.html

It has both a color quantization approach and a KMeans approach, which is combined.

Answer 4

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

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

  1b. For each rectangle, assign pixels to the space (color, frequency)

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

  2a. Determine the color of the i-th circuit (for example, i = 1 background color) by scanning the "upper frequency", "second frequency" (that is, f_R [i ,:]) for each block.

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

  2c. The best scorer for everyone I will be the i-th color of the scheme.

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 it directly on calculating the background color, or select a secondary color, and if the V HSV difference is too low, set the color from the calculated color of the circuit, but increase the V value.

pseudo code:

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 foregoing, it is clear that if there is an area with slight variability, it will have the same second color as the most common color. To adjust, the second most common color in this case can be zero, which could be protected from:

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

Answer 5

Color quantization is the same process that is used to select a palette for low-quality GIFs. To get the color palette from the photographic image, I used Nick Rabinowitz quantize.js , which is based on Leptonicas MMCQ (modified mid-slice quantization).

Live web application .

Answer 6

Name of the type of algorithm required Color quantization .

Unfortunately, I do not have the source code for you, but I am sure that google search might turn something upside down.

In particular, Dr. An article by the Dobb Journal on this subject seems promising.

Answer 7

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

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

If there is another strong peak that becomes even larger when you get to the baseline, you have found the background color. A gradient background will smooth this peak, and peak changes - when entering or exiting a new line - will be smoothed by smoothing.

Answer 8

Like the McWafflestix solution, the specifics need to be changed, but my overall approach will be ...

(I agree that HSV is the right space)

• Take a histogram of the image, filter it to smooth out the noise, and find the highest score where V and S are in the (possibly dynamic) gamut of possible “plot” colors. A red bird in the blue sky will require us to be smart enough not to base our pattern on blue, but on red. This may require some guesswork about the composition of the photograph, for example, “concentrated in the frame” and the “rule of the third” analysis may give you the possibility that the color will be relevant. Despite this, this is our base color.

• Using the Cooler line, calculate the colors that complement the base by moving the color wheel. Extra points for a calculated compliment, if it is also noticeably displayed on the histogram from step 1.

• Use the base color and calculated compliments to get nice complementary colors, such as lighter and darker versions of each, more or less saturated, etc.

Answer 9

I'm a little late for this, but I would have done a Kohonen map (http://en.wikipedia.org/wiki/Self-organizing_map) in three-dimensional color space. The number of points on the map will be the number of different colors that you want for your palette, and then train the map using all the pixels in the image. I have not tried this myself, but I am sure that someone else has already thought about it.

Answer 10

Below are some suggestions and discussions on various approaches for creating a color scheme from an image:

First, paste / draw pixels in some color space. It can be RGB, HSL or other color space. To generate a color scheme, you can use one of the following functions:

• Creating a color space histogram . This includes dividing the space into a grid and counting the pixels in each grid cell. Select the top N-cells (histograms) with the largest number of pixels and average the pixels in each to create a color per cell. It could be your color scheme.

• Median Cut or some other method of splitting space is a good improvement over C # 1, as it will split the space while viewing the data.

• Pixel clustering - grouping pixels into groups using one of the many clustering methods (k-means, average offset, etc.). Then average the pixels in each group to create a color scheme.

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

I also wrote an interactive web application that allows you to upload an image creating a color palette using one of the three above approaches, you can find the code for it on github

Answer 11

The average value of hue, saturation and brightness is maintained while maintaining the values ​​of min / max.

Block the target hue of all colors on average and interpolate the saturation and brightness for x points between the borders. This should return the circuit with a color different from the photo, but with a simple change. You might even take a look at Apple.

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