Determining a dominant color of an image based on pixel components

• US 9,870,626 B2
• Filed: 12/20/2016
• Issued: 01/16/2018
• Est. Priority Date: 12/15/2014
• Status: Active Grant

• Current Assignee: Flipboard Incorporated
• Original Assignee: Flipboard Incorporated
• Inventors: Guo, Meng
• Primary Examiner(s): AZARIAN, SEYED H
• Application Number:
  US15/385,396
• Publication Number:
  US 20170103547A1
• Time in Patent Office: 392 Days
• Field of Search: 382100, 382103, 382106, 382162-167, 382172-173, 382255, 382181, 382189-194, 382209, 382219, 382224, 382232, 382254, 382274-276, 382286-291, 382305, 382312, 706 52, 705 2661, 3482072
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G09G 5/02 characterised by the way in which colour is displayed details of colour display specific for CRTs G09G1/28; specific for flat matrix panels other than liquid crystal displays G09G3/2003; specific for liquid crystal displays G09G3/3607

Abstract

A digital magazine server determines a dominant color present in an image using a clustering algorithm. Color components of each pixel in the image are identified used to generate vectors associated with each pixel. Based on the vectors associated with the pixels, clusters including one or more pixels are generated using a clustering algorithm (e.g., k-means). The digital magazine server generates a characteristic vector for each cluster based on the vectors included in the cluster and selects a set of clusters based on their characteristic vectors. A centroid identifying the dominant color of the image is determined from the characteristic vectors of clusters in the set.

Claims

1. A method comprising:

obtaining a content item for presentation to a user, wherein the obtained content item includes an image comprising a plurality of pixels;

identifying one or more color components associated with each pixel in the plurality of pixels;

generating a characteristic vector for each sub-set of pixels, a characteristic vector for a sub-set of pixels specifying a color associated with a plurality of pixels in the sub-set by;

associating weights with the one or more color components associated with an identified pixel of the sub-set;

associating one or more additional weights with the one or more color components associated with one or more additional pixels of the sub-set; and

generating a vector for the identified pixel based at least in part on the weights, the one or more color components associated with the identified pixel, the one or more additional weights, and the one or more color components associated with the one or more additional pixels

ranking the generated one or more sub-sets of pixels based on magnitudes of the characteristic vectors of the one or more sub-sets of pixels; and

selecting one or more sub-sets of pixels having at least a threshold position in the ranking;

determining a dominant color associated with the image based on the characteristic vectors for a selected number of sub-sets of pixels;

selecting an element for inclusion in the image based on the dominant color associated with the image; and

generating a modified image including the image and the selected element.

2. The method of claim 1, wherein determining a dominant color associated with the image based on the characteristic vectors for a selected number of sub-sets of pixels comprises:

determining a centroid based on the characteristic vector for each sub-set of pixels in the selected number of sub-sets of pixels, the centroid identifying a dominant color associated with the image.

3. The method of claim 1, wherein the one or more color components associated with a pixel of the image are identified from a set of color components associated with each pixel in the image based on a color model representing the image.

4. The method of claim 1, wherein generating a characteristic vector for each sub-set of pixels comprises:

generating a vector for each identified pixel based at least in part on the one or more color components associated with each identified pixel and one or more color components of one or more additional pixels within a threshold distance of each identified pixel; and

generating one or more sub-sets of pixels, each sub-set including one or more pixels based at least in part on the generated vectors.

5. The method of claim 4, wherein generating the one or more sub-sets of pixels comprises:

determining whether to include a pixel in a sub-set of pixels based on a distance between a vector associated with the pixel and a mean value associated with the sub-set of pixels.

6. The method of claim 4, wherein a sum of magnitudes of vectors associated with pixels included in a sub-set of pixels is less than a threshold value.

7. The method of claim 4, further comprising:

selecting the selected number of the sub-sets of pixels based at least in part on the characteristic vectors, wherein selecting the selected number of the sub-sets of pixels comprises;

scoring the generated one or more sub-sets of pixels based on the characteristic vectors of the generated one or more sub-sets of pixels and a number of pixels included in each sub-set;

ranking the generated one or more sub-sets of pixels based on the scores; and

selecting one or more sub-sets of pixels having at least a threshold position in the ranking.

8. The method of claim 1, wherein selecting the element for inclusion in the image based at least in part on the dominant color associated with the image comprises:

associating a color with the element that contrasts with the dominant color.

9. A non-transitory computer readable storage medium storing executable computer program instructions, the computer program instructions comprising instructions that when executed cause a computer processor to:

obtain a content item for presentation to a user, wherein the obtained content item includes an image comprising a plurality of pixels;

identify one or more color components associated with each pixel in the plurality of pixels;

generate a characteristic vector for each sub-set of pixels, a characteristic vector for a sub-set of pixels specifying a color associated with a plurality of pixels in the sub-set by;

associating weights with the one or more color components associated with an identified pixel of the sub-set;

associating one or more additional weights with the one or more color components associated with one or more additional pixels of the sub-set; and

generating a vector for the identified pixel based at least in part on the weights, the one or more color components associated with the identified pixel, the one or more additional weights, and the one or more color components associated with the one or more additional pixels

ranking the generated one or more sub-sets of pixels based on magnitudes of the characteristic vectors of the one or more sub-sets of pixels; and

selecting one or more sub-sets of pixels having at least a threshold position in the ranking;

determine a dominant color associated with the image based on the characteristic vectors for a selected number of sub-sets of pixels;

selecting an element for inclusion in the image based on the dominant color associated with the image; and

generating a modified image including the image and the selected element.

10. The computer readable medium of claim 9, wherein the instructions that cause the processor to determine a dominant color associated with the image based on the characteristic vectors for a selected number of sub-sets of pixels comprise instructions that cause the processor to:

determine a centroid based on the characteristic vectors for each sub-set of pixels in the selected number of sub-sets of pixels, the centroid identifying a dominant color associated with the image.

11. The computer readable medium of claim 9, wherein the one or more color components associated with a pixel of the image are identified from a set of color components associated with each pixel in the image based on a color model representing the image.

12. The computer readable medium of claim 9, wherein the instructions that cause the processor to generate a characteristic vector for each sub-set of pixels comprise instructions that cause the processor to:

generate a vector for each identified pixel based at least in part on the one or more color components associated with each identified pixel and one or more color components of one or more additional pixels within a threshold distance of each identified pixel; and

generate one or more sub-sets of pixels, each sub-set including one or more pixels based at least in part on the generated vectors.

13. The computer readable medium of claim 12, wherein the instructions that cause the processor to generate one or more sub-sets of pixels comprise instructions that cause the processor to:

determine whether to include a pixel in a sub-set of pixels based on a distance between a vector associated with the pixel and a mean value associated with the sub-set of pixels.

14. The computer readable medium of claim 12, wherein a sum of magnitudes of vectors associated with pixels included in a sub-set of pixels is less than a threshold value.

15. The computer readable medium of claim 12, wherein the instructions that cause the processor to generate a characteristic vector for each sub-set of pixels further comprise instructions that cause the processor to:

select the selected number of the sub-sets of pixels based at least in part on the characteristic vectors, wherein selecting the selected number of the sub-sets of pixels comprises instructions that cause the processor to;

score the generated one or more sub-sets of pixels based on the characteristic vectors of the generated one or more sub-sets of pixels and a number of pixels included in each sub-set;

rank the generated one or more sub-sets of pixels based on the scores; and

select one or more sub-sets of pixels having at least a threshold position in the ranking.

16. The computer readable medium of claim 12, wherein the instructions that cause the processor to select the element for inclusion in the image based at least in part on the dominant color associated with the image comprises instructions that cause the processor to:

associate a color with the element that contrasts with the dominant color.